/*****************************************************************************
 *
 * 文件名称: leetcode.c
 *
 * 功能摘要: leetcode编程题
 *
 * 创建时间: 2014-12-31 16:00
 *
 * 文件版本: 0.1
 *
 * 文件作者: llxwj
 *
 * Copyright (C) 2012 All rights reserved.
 *
 *****************************************************************************
 *
 * 修改记录:
 *
 ****************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>
#include <CUnit/CUnit.h>
#include <CUnit/Basic.h>
#include <CUnit/TestDB.h>

#define bool int
#define true 1
#define false 0
#define ARRAY_NUM(x) ((sizeof(x) / sizeof(x[0])))

typedef void list_t;

/*****************************************************************************
 * 单链表
 ****************************************************************************/
typedef struct ListNode
{
	int val;
	struct ListNode *next;
}ListNode;

static struct ListNode* ListAppend(struct ListNode* head, int val)
{
	struct ListNode* p = NULL;
	struct ListNode* t = NULL;

	p = (struct ListNode*)malloc(sizeof(struct ListNode));
	if(p != NULL)
	{
		p->val = val;
		p->next = NULL;
	}

	if(head == NULL)
	{
		return p;
	}

	t = head;
	while(t->next != NULL)  t = t->next;
	t->next = p;

	return head;
}

static int ListLength(struct ListNode* head)
{
	int l = 0;

	while(head != NULL)
	{
		head = head->next;
		l++;
	}

	return l;
}

static struct ListNode* ListDestroy(struct ListNode* head)
{
	struct ListNode* t = NULL;

	while(head != NULL)
	{
		t = head;
		head = head->next;
		free(t);
	}

	return NULL;
}

static void ListPrint(ListNode* head)
{
	while(head)
	{
		printf("%d->", head->val);
		head=head->next;
	}
	printf("\n");
}

static ListNode* ListMakeCycle(ListNode* head, int k)
{
	ListNode* tail = NULL;
	ListNode* dest = NULL;
	int index = 0;
	int length = 0;

	if((head == NULL) || (k < 0)) return NULL;

	tail = head;
	while(tail->next != NULL)
	{
		tail = tail->next;
		length++;
	}

	if(length < k) return NULL;

	dest = head;
	while((dest->next != NULL) && (index < k))
	{
		dest = dest->next;
		index++;
	}

	tail->next = dest;
	return tail;
}

typedef int (*visit_func_t)(void* context, void* data, unsigned long size);
typedef int (*cmp_func_t)(void* data1, void* data2);
#define LBE_ERR_FOREACH_STOP (-40)
#define LBE_ERR_FIND_STOP (-41)
#define LBE_ERR_FIND (-6)

static int ListForeach(ListNode* list, void* context, visit_func_t visit)
{
	ListNode* node = NULL;

	if((list == NULL) || (visit == NULL))
	{
		return -1;
	}

	for(node = list; node != NULL; node = node->next)
	{
		if(visit(context, (void*)node->val, 0) == LBE_ERR_FOREACH_STOP)
		{
			break;
		}
	}

	return 0;
}

int ListFind(ListNode* list, void* data, cmp_func_t cmp)
{
	ListNode* node = NULL;
	int index = 0;

	if((list == NULL) || (cmp == NULL))
	{
		return -1;
	}

	for(node = list; node != NULL; node = node->next)
	{
		if(cmp(data, (void*)node->val) == 0)
		{
			return index;
		}
		index++;
	}

	return LBE_ERR_FIND;
}

int ListGet(ListNode* list, int index, void** data)
{
	ListNode* node = NULL;

	if((list == NULL) || (index < 0) || (data == NULL)) 
	{
		return -1;
	}

	for(node = list; (node != NULL) && (index > 0); node = node->next)
	{
		index--;
	}

	*data = (void*)(node->val);

	return 0;
}

/*****************************************************************************
 * 队列
 ****************************************************************************/
typedef struct QueueNode
{
	void* data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	int size;
	struct QueueNode* list;
}Queue;

static QueueNode* QueueNodeAppend(QueueNode* head, void* data)
{
	QueueNode* p = NULL;
	QueueNode* t = NULL;

	p = (QueueNode*)malloc(sizeof(QueueNode));
	if(p != NULL)
	{
		p->data = data;
		p->next = NULL;
	}

	if(head == NULL)
	{
		return p;
	}

	t = head;
	while(t->next != NULL)  t = t->next;
	t->next = p;

	return head;
}

static void QueueNodeDestroy(QueueNode* head)
{
	QueueNode* t = NULL;

	while(head != NULL)
	{
		t = head;
		head = head->next;
		free(t);
	}
}

static Queue* QueueNew(void)
{
	Queue* q = NULL;

	q = (Queue*)malloc(sizeof(Queue));
	if(q != NULL)
	{
		q->list = NULL;
		q->size = 0;
	}

	return q;
}

static void QueueDestroy(Queue* q)
{
	if(q == NULL)
	{
		return;
	}

	if(q->list != NULL)
	{
		QueueNodeDestroy(q->list);
	}

	free(q);
}

static void QueuePush(Queue* q, void* data)
{
	if(q == NULL)
	{
		return;
	}

	q->list = QueueNodeAppend(q->list, data);
}

static void* QueuePop(Queue* q)
{
	QueueNode* head = NULL;
	void* data = NULL;

	if(q == NULL)
	{
		return NULL;
	}

	if(q->list == NULL)
	{
		return NULL;
	}

	head = q->list;
	q->list= q->list->next;
	data = head->data;
	free(head);
	return data;
}

static bool QueueIsEmpty(Queue* q)
{
	if(q == NULL)
	{
		return true;
	}

	if(q->list == NULL)
	{
		return true;
	}

	return false;
}

static int QueueSize(Queue* q)
{
	int size = 0;
	QueueNode* node = NULL;

	if(q == NULL)
	{
		return 0;
	}

	if(q->list == NULL)
	{
		return 0;
	}

	node = q->list;
	while(node != NULL)
	{
		node = node->next;
		size++;
	}
	return size;
}

/*****************************************************************************
 * 栈
 ****************************************************************************/
typedef struct StackNode
{
	void* data;
	struct StackNode* next;
}StackNode;
typedef struct Stack
{
	int size;
	StackNode* list;
}Stack;

static StackNode* StackNodeAppend(StackNode* head, void* data)
{
	StackNode* p = NULL;
	StackNode* t = NULL;

	p = (StackNode*)malloc(sizeof(StackNode));
	if(p != NULL)
	{
		p->data = data;
		p->next = NULL;
	}

	if(head == NULL)
	{
		return p;
	}

	t = head;
	while(t->next != NULL)  t = t->next;
	t->next = p;

	return head;
}

static void StackNodeDestroy(StackNode* head)
{
	StackNode* t = NULL;

	while(head != NULL)
	{
		t = head;
		head = head->next;
		free(t);
	}
}

static Stack* StackNew(void)
{
	Stack* s = NULL;

	s = (Stack*)malloc(sizeof(Stack));
	if(s != NULL)
	{
		s->list = NULL;
	}

	return s;
}

static void StackDestroy(Stack* s)
{
	if(s == NULL)
	{
		return;
	}

	if(s->list != NULL)
	{
		StackNodeDestroy(s->list);
		s->list = NULL;
	}

	free(s);
}

static bool StackIsEmpty(Stack* s)
{
	if(s == NULL)
	{
		return true;
	}

	if(s->list == NULL)
	{
		return true;
	}

	return false;
}

static void StackPush(Stack* s, void* data)
{
	if(s == NULL)
	{
		return;
	}

	s->list = StackNodeAppend(s->list, data);
}

static void* StackPop(Stack* s)
{
	StackNode* p = NULL;
	StackNode* n = NULL;
	void* data = NULL;

	if(s == NULL)
	{
		return NULL;
	}

	if(s->list == NULL)
	{
		return NULL;
	}

	n = s->list;
	while(n->next != NULL)
	{
		p = n;
		n = n->next;
	}

	if(p == NULL)
	{
		data = n->data;
		free(p);
		s->list = NULL;
	}
	else
	{
		p->next = NULL;
		data = n->data;
		free(n);
	}

	return data;
}

static void StackTop(Stack* s, void** data)
{
	StackNode* n = NULL;

	if((s == NULL) || (data == NULL))
	{
		return;
	}

	if(s->list == NULL)
	{
		return;
	}

	n = s->list;
	while(n->next != NULL)
	{
		n = n->next;
	}

	*data = n->data;
}

static int StackSize(Stack* s)
{
	int size = 0;
	StackNode* node = NULL;

	if(s == NULL)
	{
		return 0;
	}

	if(s->list == NULL)
	{
		return 0;
	}

	node = s->list;
	while(node != NULL)
	{
		node = node->next;
		size++;
	}
	return size;
}

/*****************************************************************************
 * 二叉树
 ****************************************************************************/
typedef struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
	struct TreeNode* next;
	struct TreeNode* parent;
}TreeNode, TreeLinkNode;

static TreeNode* TreeNew(int val, TreeNode* l, TreeNode* r, TreeNode* p)
{
	TreeNode* t = NULL;

	t = (TreeNode*)malloc(sizeof(TreeNode));
	if(t != NULL)
	{
		t->val = val;
		t->left = l;
		t->right = r;
		t->next = NULL;
		t->parent = p;
	}
	return t;
}

static TreeNode* TreeAppend(TreeNode* root, int val)
{
	if(root == NULL)
	{
		return TreeNew(val, NULL, NULL, NULL);
	}
	return root;
}

static void TreeGetNodesNumber(struct TreeNode* root, int* n)
{
    if(root != NULL)
    {
       *n = *n + 1;
       TreeGetNodesNumber(root->left, n);
       TreeGetNodesNumber(root->right, n);
    }
 
} 

/*****************************************************************************
 * Min Stack
 ****************************************************************************/
typedef struct
{
	Stack* noraml;
	Stack* min;
}MinStackPriv;
typedef struct MinStack
{
	void (*push)(struct MinStack* ms, int x);
	void (*pop)(struct MinStack* ms);
	int (*top)(struct MinStack* ms);
	int (*getMin)(struct MinStack* ms);
	char priv[0];
}MinStack;

void MinStackPush(MinStack* ms, int x)
{
	MinStackPriv* priv = NULL;
	int val = 0;

	if(ms == NULL) return;

	priv = (MinStackPriv*)ms->priv;

	StackPush(priv->noraml, (void*)x);
	if(StackIsEmpty(priv->min))
	{
		StackPush(priv->min, (void*)x);
	}
	else
	{
		StackTop(priv->min, (void**)&val);
		if(x <= val)
		{
			StackPush(priv->min, (void*)x);
		}
	}
}

void MinStackPop(MinStack* ms)
{
	int normal_top = 0;
	int min_top = 0;
	MinStackPriv* priv = NULL;

	if(ms == NULL) return;

	priv = (MinStackPriv*)ms->priv;

	StackTop(priv->min, (void**)&min_top);
	StackTop(priv->noraml, (void**)&normal_top);

	StackPop(priv->noraml);
	if(min_top == normal_top)
	{
		StackPop(priv->min);
	}
}

int MinStackTop(MinStack* ms)
{
	int top = 0;
	MinStackPriv* priv = NULL;

	if(ms == NULL) return INT_MIN;

	priv = (MinStackPriv*)ms->priv;
	StackTop(priv->noraml, (void**)&top);
	return top;
}

int MinStackGetMin(MinStack* ms)
{
	int min = 0;
	MinStackPriv* priv = NULL;

	if(ms == NULL) return INT_MIN;

	priv = (MinStackPriv*)ms->priv;
	StackTop(priv->min, (void**)&min);
	return min;
}

MinStack* MinStackNew(void)
{
	MinStack* ms = NULL;
	MinStackPriv* priv = NULL;

	ms = malloc(sizeof(MinStack) + sizeof(MinStackPriv));
	if(ms == NULL)
	{
		return NULL;
	}

	priv = (MinStackPriv*)ms->priv;

	priv->min = StackNew();
	priv->noraml = StackNew();

	ms->push = MinStackPush;
	ms->pop = MinStackPop;
	ms->top = MinStackTop;
	ms->getMin = MinStackGetMin;

	return ms;
}

void MinStackFree(MinStack* ms)
{
	MinStackPriv* priv = NULL;

	if(ms != NULL)
	{
		priv = (MinStackPriv*)ms->priv;
		StackDestroy(priv->min);
		StackDestroy(priv->noraml);
		free(ms);
	}
}

/*****************************************************************************
 * Two Sum
 ****************************************************************************/
typedef struct
{
	int number;
	int count;
}TwoSumTemplatet;

typedef struct
{
	ListNode* list;
}TwoSumPriv;

typedef struct
{
	ListNode* list;
	int value;
	bool find;
}TwoSumContext;

typedef struct TwoSum
{
	void (*add)(struct TwoSum* ts, int number);
	bool (*find)(struct TwoSum* ts, int value);
	char priv[0];
}TwoSum;

static int TwoSumCompare(void* data1, void* data2)
{
	TwoSumTemplatet* tst1 = data1;
	TwoSumTemplatet* tst2 = data2;

	if((tst1 == NULL) || (tst2 == NULL))
	{
		return -1;
	}

	if(tst1->number == tst2->number)
	{
		return 0;
	}
	else if(tst1->number > tst2->number)
	{
		return 1;
	}
	else
	{
		return -1;
	}
}

static void TwoSumAdd(TwoSum* ts, int number)
{
	TwoSumPriv* priv = NULL;
	TwoSumTemplatet* tst = NULL;
	TwoSumTemplatet* old = NULL;
	int index = 0;

	if(ts == NULL) return;
	priv = (TwoSumPriv*)ts->priv;

	tst = malloc(sizeof(TwoSumTemplatet));
	if(tst == NULL) return;

	tst->number = number;
	tst->count = 1;

	index = ListFind(priv->list, tst, TwoSumCompare);
	if(index >= 0)
	{
		ListGet(priv->list, index, (void**)&old);
		old->count++;
		free(tst);
	}
	else
	{
		ListAppend(priv->list, (int)tst);
	}
}

static int TwoSumForeach(void* context, void* data, unsigned long size)
{
	TwoSumContext* tsc = NULL;
	TwoSumTemplatet* tst = NULL;
	TwoSumTemplatet another = {0};
	int index = 0;

	tsc = context;
	tst = data;

	another.number = tsc->value - tst->number;
	if((another.number == tst->number) && (tst->count > 1))
	{
		tsc->find = true;
		return LBE_ERR_FOREACH_STOP;
	}
	else if(another.number != tst->number)
	{
		index = ListFind(tsc->list, &another, TwoSumCompare);
		if(index >= 0)
		{
			tsc->find = true;
			return LBE_ERR_FOREACH_STOP;
		}
	}

	return 0;
}

static bool TwoSumFind(TwoSum* ts, int value)
{
	TwoSumPriv* priv = NULL;
	TwoSumContext tsc = {0};

	priv = (TwoSumPriv*)ts->priv;

	tsc.find = false;
	tsc.list = priv->list;
	tsc.value = value;

	ListForeach(priv->list, &tsc, TwoSumForeach);
	return tsc.find;
}

static TwoSum* TwoSumNew()
{
	TwoSum* ts = NULL;
	TwoSumPriv* priv = NULL;

	ts = (TwoSum*)malloc(sizeof(TwoSum) + sizeof(TwoSumPriv));
	if(ts == NULL)
	{
		return NULL;
	}

	priv = (TwoSumPriv*)ts->priv;
	priv->list = NULL;
	//priv->list = ListNew(lbe_free);

	ts->add = TwoSumAdd;
	ts->find = TwoSumFind;

	return ts;
}

static void TwoSumFree(TwoSum* ts)
{
	TwoSumPriv* priv = NULL;

	priv = (TwoSumPriv*)ts->priv;
	ListDestroy(priv->list);
	free(ts);
}

/*****************************************************************************
 * OJ's Binary Tree Serialization:
 * The serialization of a binary tree follows a level order traversal, where
 * '#' signifies a path terminator where no node exists below.
 * Here's an example:
 *   1
 *  / \
 * 2   3
 *     /
 *    4
 *     \
 *      5
 * The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 ****************************************************************************/
static TreeNode* TreeNewByStringOJ(const char* s)
{
	TreeNode* root = NULL;
	TreeNode* p = NULL;
	int val = 0;
	Queue* q = NULL;
	int negative = 1;

	q = QueueNew();

	if(s == NULL) return NULL;
	if(*s != '{') return NULL;
	s++;
	while((*s != '\0') && (*s != ',') && (*s != '}'))
	{
		if(*s == '-')
		{
			negative = -1;
		}
		else
		{
			val = val * 10 + (*s - '0');
		}
		s++;
	}
	s++;

	root = TreeNew(val * negative, NULL, NULL, NULL);
	QueuePush(q, root);
	while(!QueueIsEmpty(q) && (*s != '\0'))
	{
		p = QueuePop(q);

		if(*s != '#')
		{
			val = 0;
			negative = 1;
			while((*s != ',') && (*s != '\0') && (*s != '}'))
			{
				val = val * 10 + (*s - '0');
				s++;
			}
			s++;
			p->left = TreeNew(val * negative, NULL, NULL, p);
			QueuePush(q, p->left);
		}
		else
		{
			s++; //jump '#'
			if(*s == '\0') break;
			s++; //jump ','
			if(*s == '\0') break;
		}

		if(*s == '\0') break;

		if(*s != '#')
		{
			val = 0;
			negative = 1;
			while((*s != ',') && (*s != '\0') && (*s != '}'))
			{
				if(negative == '-')
				{
					negative = -1;
				}
				else
				{
					val = val * 10 + (*s - '0');
				}
				s++;
			}
			s++;
			p->right = TreeNew(val * negative, NULL, NULL, p);
			QueuePush(q, p->right);
		}
		else
		{
			s++; //jump '#'
			if(*s == '\0') break;
			s++; //jump ','
			if(*s == '\0') break;
		}
	}

	QueueDestroy(q);
	return root;
}

/*****************************************************************************
 * Myself Binary Tree Serialization:
 * The serialization of a binary tree use preorder traversal sequence, where
 * '#' signifies a path terminator where no node exists below.
 * Here's an example:
 *   1
 *  / \
 * 2   3
 *     /
 *    4
 *     \
 *      5
 * The above binary tree is serialized as "1,2,#,#,3,4,#,5,#,#,".
 ****************************************************************************/
static TreeNode* TreeNewByString(const char* s)
{
	TreeNode* root = NULL;
	TreeNode* p = NULL;
	bool has_left = true;
	int val = 0;

	if(s == NULL)
	{
		return NULL;
	}

	if((s[0] == '#') && (s[1] == ',') && (s[2] == '#'))
	{
		return NULL;
	}

	while(*s != ',')
	{
		val = val * 10 + (*s - '0');
		s++;
	}
	s++;

	root = TreeNew(val, NULL, NULL, NULL);
	p = root;
	while(*s != '\0')
	{
		if(*s == '#')
		{
			if(has_left)
			{
				has_left = false;
			}
			else
			{
				p = p->parent;
			}
			s++;
			s++;
			continue;
		}

		val = 0;
		while((*s != ',') && (*s != '\0'))
		{
			val = val * 10 + (*s - '0');
			s++;
		}
		s++;

		if(has_left)
		{
			p->left = TreeNew(val, NULL, NULL, p);
			p = p->left;
			has_left = true;
		}
		else
		{
			p->right = TreeNew(val, NULL, NULL, p);
			p = p->right;
			has_left = true;
		}
	}

	return root;
}

static TreeNode* TreeDestroy(TreeNode* root)
{
	if(root == NULL) return NULL;

	if(root->left != NULL)
	{
		TreeDestroy(root->left);
		root->left = NULL;
	}
	if(root->right != NULL)
	{
		TreeDestroy(root->right);
		root->right = NULL;
	}
	if((root->left == NULL) && (root->right == NULL))
	{
		free(root);
	}

	return NULL;
}

static int TreeDepth(struct TreeNode* root)
{
	int left_depth = 0;
	int right_depth = 0;

	if(root == NULL) return 0;
	left_depth = TreeDepth(root->left);
	right_depth = TreeDepth(root->right);
	return (left_depth > right_depth ? left_depth : right_depth) + 1;
}

static int TreeHeight(struct TreeNode* root)
{
	int left_height = 0;
	int right_height = 0;

	if(root == NULL) return -1;
	left_height = TreeHeight(root->left);
	right_height = TreeHeight(root->right);
	return (left_height > right_height ? left_height : right_height) + 1;
}

static void TreePreorder(TreeNode* root)
{
	if(root == NULL) return;
	printf("%d ", root->val);
	if(root->left != NULL)
	{
		TreePreorder(root->left);
	}
	else
	{
		printf("# ");
	}
	if(root->right != NULL)
	{
		TreePreorder(root->right);
	}
	else
	{
		printf("# ");
	}
}

static void TreeInorder(TreeNode* root)
{
	if(root == NULL) return;
	if(root->left != NULL)
	{
		TreeInorder(root->left);
	}
	else
	{
		printf("# ");
	}
	printf("%d ", root->val);
	if(root->right != NULL)
	{
		TreeInorder(root->right);
	}
	else
	{
		printf("# ");
	}
}

static void TreePostorder(TreeNode* root)
{
	if(root == NULL) return;
	if(root->left != NULL) TreePostorder(root->left);
	if(root->right != NULL) TreePostorder(root->right);
	printf("%d ", root->val);
}

/*****************************************************************************
 * 2:Add Two Numbers
 * You are given two linked lists representing two non-negative numbers. The
 * digits are stored in reverse order and each of their nodes contain a
 * single digit. Add the two numbers and return it as a linked list.
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * 解释: 342
 *      +465 = 807-> 反序就是708
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/add-two-numbers/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 *
 * 解法:
 * L1   NULL NOTNULL NULL    NOTNULL
 * L2   NULL NULL    NOTNULL NOTNULL
 * 返回  NULL L1      L2      (Equal Length or Not Equal Length)
 ****************************************************************************/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) 
{
	struct ListNode* p1 = NULL;
	struct ListNode* p2 = NULL;
	struct ListNode* l3 = NULL;
	int carry = 0;
	int val = 0;

	if((l1 == NULL) && (l2 == NULL)) return NULL;
	if((l1 == NULL) && (l2 != NULL)) return l2;
	if((l1 != NULL) && (l2 == NULL)) return l1;

	p1 = l1;
	p2 = l2;
	while((p1 != NULL) && (p2 != NULL))
	{
		val = p1->val + p2->val + carry;
		carry = val / 10;
		l3 = ListAppend(l3, val % 10);
		p1 = p1->next;
		p2 = p2->next;
	}

	if(p1 != NULL)
	{
		while(p1 != NULL)
		{
			val = p1->val + carry;
			carry = val / 10;
			ListAppend(l3, val % 10);
			p1 = p1->next;
		}
		if(carry != 0)
		{
			ListAppend(l3, carry);
			carry = 0;
		}
	}

	if(p2 != NULL)
	{
		while(p2 != NULL)
		{
			val = p2->val + carry;
			carry = val / 10;
			ListAppend(l3, val % 10);
			p2 = p2->next;
		}
		if(carry != 0)
		{
			ListAppend(l3, carry);
			carry = 0;
		}
	}

	if(carry != 0)
	{
		ListAppend(l3, carry);
	}

	return l3;
}

/*****************************************************************************
 * 6: ZigZag Conversion
 * The string "PAYPALISHIRING" is written in a zigzag pattern on a given
 * number of rows like this: (you may want to display this pattern in a fixed
 * font for better legibility)
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * And then read line by line: "PAHNAPLSIIGYIR"
 * Write the code that will take a string and make this conversion given a
 * number of rows:
 * string convert(string text, int nRows);
 * convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/zigzag-conversion/
 *
 * Code:
 * char* convert(char* s, int numRows) {
 * 
 * }
 *
 * n_rows:
 * 1:  1 2 3 4 5 6 ... ... gap = 0
 * 2:  1  3  5  7          gap = 2
 *     2  4  6  8
 *     return 1357...2468
 * 3:  1   5    9          gap = 4
 *     2 4 6 8 10
 *     3   7   11
 *     return 159...2468,10...37,11...
 * 4:  1      7        13  gap = 6
 *     2   6  8     12 14
 *     3 5    9  11    15
 *     4     10        16
 *     return 1,7,13...2,6,8,12,14,...3,5,9,11,15,...,4,10,16...
 *
 * 我们发现如下规律,共有n行：
 * 1 第i行从i开始
 * 2 第一行与最后一行间隔是2(n-1)
 * 2 中间第i行两个数的间隔是2(n-i),2(i-1)交替[如果i从0起则是2(n-i-1),2i交替]
 * 如有四行的情况:每行的起始都是,1,2,3,4
 * 第一行间隔:2(4-1)=6
 * 第二行间隔:2(4-2)=4,2(2-1)=2,
 * 第三行间隔:2(4-3)=2,2(3-1)=4,
 * 第四行间隔:2(4-1)=6
 ****************************************************************************/
char* convert(char* s, int numRows)
{
	int n = 0;
	char* p = s;
	int i = 0;
	int j = 0;
	bool flag = true;
	char* _006_str = NULL;
	int m = 0;

	if(s == NULL) return s;
	if(*s == 0) return s;
	if(numRows <= 1) return s;

	_006_str = (char*)malloc(strlen(s) + 1);
	memset(_006_str, 0, strlen(s) + 1);
	while(*p)
	{
		p++;
		n++;
	}

	for(i = 0; i < numRows; i++)
	{
		j = i;
		flag = true;
		while(j < n)
		{
			_006_str[m++] = s[j];
			if((i == 0) || (i == (numRows - 1)))
			{
				j = j + 2 * (numRows - 1);
			}
			else
			{
				if(flag)
				{
					flag = false;
					j = j + 2 * (numRows - i - 1);
				}
				else
				{
					flag = true;
					j = j + 2 * i;
				}
			}
		}
	}

	return _006_str;
}

/*****************************************************************************
 * 7: Reverse Integer
 * Reverse digits of an integer.
 * Example1: x = 123, return 321
 * Example2: x = -123, return -321
 *
 * Have you thought about this?
 * Here are some good questions to ask before coding. Bonus points for you
 * if you have already thought through this!
 *
 * If the integer's last digit is 0, what should the output be? ie, cases
 * such as 10, 100.
 *
 * Did you notice that the reversed integer might overflow? Assume the input
 * is a 32-bit integer, then the reverse of 1000000003 overflows. How should
 * you handle such cases?
 *
 * For the purpose of this problem, assume that your function returns 0 when
 * the reversed integer overflows.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/reverse-integer/
 *
 * Code:
 * int reverse(int x) {
 * }
 ****************************************************************************/
int reverse(int x)
{
	int64_t result = 0;
	int64_t remainder = 0;

	while(x != 0)
	{
		remainder = x % 10;
		result = result * 10 + remainder;
		x = x / 10;
	}

	if((result > INT_MAX) || (result < INT_MIN))
	{
		return 0;
	}

	return result;
}

/*****************************************************************************
 * 8:String to Integer (atoi)
 * Implement atoi to convert a string to an integer.
 * Hint: Carefully consider all possible input cases. If you want a challenge,
 * please do not see below and ask yourself what are the possible input cases.
 * Notes: It is intended for this problem to be specified vaguely (ie, no
 * given input specs). You are responsible to gather all the input
 * requirements up front.
 *
 * spoilers alert... click to show requirements for atoi.
 * Requirements for atoi:
 * The function first discards as many whitespace characters as necessary
 * until the first non-whitespace character is found. Then, starting from
 * this character, takes an optional initial plus or minus sign followed by
 * as many numerical digits as possible, and interprets them as a numerical
 * value.
 *
 * The string can contain additional characters after those that form the
 * integral number, which are ignored and have no effect on the behavior of
 * this function.
 *
 * If the first sequence of non-whitespace characters in str is not a valid
 * integral number, or if no such sequence exists because either str is empty
 * or it contains only whitespace characters, no conversion is performed.
 *
 * If no valid conversion could be performed, a zero value is returned. If
 * the correct value is out of the range of representable values,
 * INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/string-to-integer-atoi/
 *
 * Code:
 * int myAtoi(char *str) {
 * }
 ****************************************************************************/
int myAtoi(char* str)
{
	int64_t result = 0;
	int negative = 1;
	int start = 0;

	if(str == NULL) return 0;
	if(*str == '\0') return 0;

	while((*str != '\0') && (result < INT_MAX) && (result > INT_MIN))
	{
		if((*str == '-') && isdigit(*(str + 1)))
		{
			negative = -1;
		}
		else if((*str == '+') && isdigit(*(str + 1)))
		{
			negative = 1;
		}
		else if(isdigit(*str))
		{
			result = result * 10 + *str - '0';
			start = 1;
		}
		else if(start == 1)
		{
			break;
		}
		else if(isspace(*str))
		{
		}
		else
		{
			break;
		}
		str++;
	}

	result = result * negative;
	if(result > INT_MAX)
	{
		return INT_MAX;
	}
	else if(result < INT_MIN)
	{
		return INT_MIN;
	}
	else
	{
		return result;
	}
}

/*****************************************************************************
 * 9:Palindrome Number
 * Determine whether an integer is a palindrome. Do this without extra space.
 * click to show spoilers.
 * Some hints:
 * Could negative integers be palindromes? (ie, -1)
 *
 * If you are thinking of converting the integer to string, note the
 * restriction of using extra space.
 *
 * You could also try reversing an integer. However, if you have solved the
 * problem "Reverse Integer", you know that the reversed integer might
 * overflow. How would you handle such case?
 * There is a more generic way of solving this problem.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/palindrome-number/
 *
 * Code:
 * bool isPalindrome(int x) {
 * }
 *
 * http://blog.163.com/hljmdjlln@126/blog/static/5473620620120412525181/
 * 有趣的数-回文数（Palindrome number）
 * 回文数是数学界中的一种有趣的现象。比如121就是一个回文数。回文数的数字互相对
 * 应，从中间一个任意一位数字起，左右每隔一个的数字都相等。回文数有许多神奇的
 * 规律和奥秘。主要分为读数回文数、平方回文数、乘积回文数以及倒乘回文数。
 * 一、读数回文数
 * 【解释】读数回文数是指一个正整数，正着读和倒着读内容一致。
 * 【举例】数字：98789
 * 正读：九万八千七百八十九（98789）
 * 倒读：九万八千七百八十九（98789）
 * 正读与倒读内容一致，所以这个数字就是读书回文数。
 * 注：读书回文数的数位都是奇数个。
 * 二、 平方回文数
 * 【解释】平方回文数是指，一个数的平方是一个回文数。
 * 【举例】11^2=121，111^2=12321，1111^2=1234321 ，122^2=484
 * 三、回文算式
 * 【解释】等号左边是两个或多个因数相乘，右边是它们的乘积或几个因数相乘。如果
 * 把每个算式中的 “×”和“=”去掉，那么，它们都变成回文数，所以，我们不妨把这些算
 * 式叫做“回文算式”。
 * 【举例】3×51=153
 * 	6×21=126
 * 4307×62=267034
 * 9×7×533=33579
 * 12×42=24×21
 * 34×86=68×43
 * 102×402=204×201
 * 1012×4202=2024×2101
 * 不知你是否注意到，如果分别把上面的回文算式等号两边的因数交换位置，得到的仍
 * 是一个回文算式。比如：
 * 42×12=21×24 ，
 * 43×68=86×34，
 * 仍是回文算式。
 * 还有更奇妙的回文算式，请看：
 * 12×231=132×21（积是2772），
 * 12×4032=2304×21（积是48384），
 * 这种回文算式，连乘积都是回文数。
 * 注：四位的回文数一定能被11整除。设它为abba，那它等于
 * a*1000+b*100+b*10+a=1001a+110b，
 * 能被11整除。
 * 另外，在数学上还有一种算式称为『回文式』。回文式即是从左右看皆通的算式。
 * 你们且看 112 x 113 = 12656 这条算式的特别之处？只要把此算式由尾写起，即成为
 * 以下式子
 * 12656 = 311 x 211，可以发现两条算式均成立。
 * 112不但乘以113有此特性，乘以某些数也有同样的效果：
 * (1) 112 x 124 = 13888 将式子由右到左写是 88831 = 421 x 211
 * (2) 112 x 133 = 14896 将式子由右到左写是 69841 = 331 x 211
 * (3) 112 x 223 = 24976 将式子由右到左写是 67942 = 322 x 211
 * 其实，某些平方数也有此结果：
 * 12 x 12=144将式子由右到左写是 441= 21 x 21
 * 13 x 13=169将式子由右到左写是 961=31 x 31
 * 经过仔细发现，我们在完全平方数，完全立方数中也找到了不少『回文』的例子，它
 * 令我们理性的数学平添了不少感性的诗情画意。
 ****************************************************************************/
bool isPalindrome(int x)
{
	int64_t result = 0;
	int64_t remainder = 0;
	int64_t backup = x;

	if(x < 0) return false;

	while(x != 0)
	{
		remainder = x % 10;
		result = result * 10 + remainder;
		x = x / 10;
	}

	if(result == backup)
	{
		return true;
	}
	else
	{
		return false;
	}
}

/*****************************************************************************
 * 13:Roman to Integer
 * Given a roman numeral, convert it to an integer.
 * Input is guaranteed to be within the range from 1 to 3999.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/roman-to-integer/
 *
 * Code:
 * int romanToInt(char* s) {
 *
 * }
 *
 * 记数方法:
 * 基本字符                I   V   X    L   C   D   M
 * 相应的阿拉伯数字表示为  1   5   10  50  100 500 1000
 * 1、相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
 * 2、小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数， 
 *    如：Ⅷ = 8；Ⅻ = 12；
 * 3、小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到
 *    的数，如：Ⅳ= 4；Ⅸ= 9；
 * 4、正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
 * 5、在一个数的上面画一条横线，表示这个数扩大1000倍。
 * 组数规则:
 * 有几条须注意掌握：
 * 1、基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用
 * 构成数目，都不能超过三个；放在大数的左边只能用一个。
 * 2、不能把基本数字V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方
 * 法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
 * 3、V 和X 左边的小数字只能用Ⅰ。
 * 4、L 和C 左边的小数字只能用X。
 * 5、D 和M 左边的小数字只能用C。
 * 对照举例:
 * 个位数举例
 * Ⅰ,1 】Ⅱ，2】 Ⅲ，3】 Ⅳ，4 】Ⅴ，5 】Ⅵ，6】Ⅶ，7】 Ⅷ，8 】Ⅸ，9 】
 * 十位数举例
 * Ⅹ，10】 Ⅺ，11 】Ⅻ，12】 XIII,13】 XIV,14】 XV,15 】XVI,16 】XVII,17 】
 * XVIII,18】 XIX,19】 XX,20】XXI,21 】XXII,22 】XXIX,29】 XXX,30】 XXXIV,34】
 * XXXV,35 】XXXIX,39】 XL,40】L,50 】LI,51】LV,55】 LX,60】LXV,65】 LXXX,80】
 * XC,90 】XCIII,93】 XCV,95 】XCVIII,98】 XCIX,99 】
 * 百位数举例
 * C,100】 CC,200 】CCC,300 】CD,400】 D,500 】DC,600 】DCC,700】 DCCC,800 】
 * CM,900】 CMXCIX,999】
 * 千位数举例
 * M,1000】 MC,1100 】MCD,1400 】MD,1500 】MDC,1600 】MDCLXVI,1666】
 * MDCCCLXXXVIII,1888 】MDCCCXCIX,1899 】MCM,1900 】MCMLXXVI,1976】
 * MCMLXXXIV,1984】 MCMXC,1990 】MM,2000 】MMMCMXCIX,3999】
 * 千位数以上举例(括号表示有上划线)
 * (LXV)CCLIX，65,259 】
 * ((CXXXIV))(CMXLV)DLXXXIV，134945584】
， (CLXXXIIIDCL)183650】
 ****************************************************************************/
int romanToInt(char* s)
{
	int result = 0;
	if(s == NULL) return 0;
	if(*s == '\0') return 0;

	while(*s != '\0')
	{
		if((s[0] == 'I') && (s[1] == 'V'))
		{
			result -= 1;
		}
		else if((s[0] == 'I') && (s[1] == 'X'))
		{
			result -= 1;
		}
		else if((s[0] == 'X') && (s[1] == 'L'))
		{
			result -= 10;
		}
		else if((s[0] == 'X') && (s[1] == 'C'))
		{
			result -= 10;
		}
		else if((s[0] == 'C') && (s[1] == 'D'))
		{
			result -= 100;
		}
		else if((s[0] == 'C') && (s[1] == 'M'))
		{
			result -= 100;
		}
		else if(s[0] == 'I')
		{
			result += 1;
		}
		else if(s[0] == 'V')
		{
			result += 5;
		}
		else if(s[0] == 'X')
		{
			result += 10;
		}
		else if(s[0] == 'L')
		{
			result += 50;
		}
		else if(s[0] == 'C')
		{
			result += 100;
		}
		else if(s[0] == 'D')
		{
			result += 500;
		}
		else if(s[0] == 'M')
		{
			result += 1000;
		}
		s++;
	}

	return result;
}

/*****************************************************************************
 * 14:Longest Common Prefix
 * Write a function to find the longest common prefix string amongst an array
 * of strings.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/longest-common-prefix/
 *
 * Code:
 * char* longestCommonPrefix(char** strs, int strsSize) {
 *
 * }
 ****************************************************************************/
char* longestCommonPrefix(char** strs, int strsSize)
{
	static char prefix[128] = {0};
	int i = 0;
	int j = 0;

	memset(prefix, 0, sizeof(prefix));

	if((strs == NULL) || (strsSize <= 0)) return prefix;

	strcpy(prefix, strs[0]);
	for(i = 1; i < strsSize; i++)
	{
		for(j = 0; (prefix[j] != '\0') && (strs[i][j] != '\0'); j++)
		{
			if(prefix[j] != strs[i][j])
			{
				break;
			}
		}
		prefix[j] = '\0';
	}

	return prefix;
}

/*****************************************************************************
 * 19:Remove Nth Node From End of List
 * Given a linked list, remove the nth node from the end of list and return
 * its head.
 * For example,
 * Given linked list: 1->2->3->4->5, and n = 2.
 * After removing the second node from the end, the linked list becomes
 * 1->2->3->5.
 * Note:
 * Given n will always be valid.
 * Try to do this in one pass.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 *
 * struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
 *
 * }
 ****************************************************************************/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
	struct ListNode* fast = NULL;
	struct ListNode* slow = NULL;
	struct ListNode* temp = NULL;

	if(head == NULL) return head;
	if(head->next == NULL)
	{
		free(head);
		return NULL;
	}

	fast = slow = head;
	n = n + 1;
	while((n > 0) && (fast != NULL))
	{
		fast = fast->next;
		n--;
	}

	if(n == 1)
	{
		temp = slow->next;
		free(slow);
		return temp;
	}

	while(fast != NULL)
	{
		slow = slow->next;
		fast = fast->next;
	}

	temp = slow->next;
	slow->next = slow->next->next;
	free(temp);

	return head;
}

/*****************************************************************************
 * 20: Valid Parentheses
 * Given a string containing just the characters '(', ')', '{', '}', '[' and
 * ']', determine if the input string is valid.
 * The brackets must close in the correct order, "()" and "()[]{}" are all
 * valid but "(]" and "([)]" are not.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/valid-parentheses/
 *
 * Code:
 * bool isValid(char* s) {
 * };
 *
 ****************************************************************************/
bool isValid(char* s)
{
	char* stack = NULL;
	int top = 0;
	char open = 0;
	bool status = true;

	if(s == NULL) return false;
	if(*s == '\0') return false;

	stack = (char*)malloc(strlen(s) + 1);
	memset(stack, 0, strlen(s) + 1);
	while(*s != '\0')
	{
		if((*s == '{') || (*s == '(') || (*s == '['))
		{
			stack[top++] = *s;
			s++;
			continue;
		}

		if(top == 0)
		{
			status = false;
			break;
		}
		else if(*s == '}')
		{
			open = stack[--top];
			if(open != '{')
			{
				status = false;
				break;
			}
		}
		else if(*s == ')')
		{
			open = stack[--top];
			if(open != '(')
			{
				status = false;
				break;
			}
		}
		else if(*s == ']')
		{
			open = stack[--top];
			if(open != '[')
			{
				status = false;
				break;
			}
		}
		s++;
	}

	if(status && top != 0)
	{
		status = false;
	}
	free(stack);

	return status;
}

/*****************************************************************************
 * 21: Merge Two Sorted Lists
 * Merge two sorted linked lists and return it as a new list. The new list
 * should be made by splicing together the nodes of the first two lists.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/merge-two-sorted-lists/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
 * }
 ****************************************************************************/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
	struct ListNode* p = NULL;
	struct ListNode* t = NULL;
	struct ListNode* h = NULL;

	if(l1 != NULL && l2 == NULL)
	{
		return l1;
	}

	if(l1 == NULL && l2 == NULL)
	{
		return l1;
	}

	if(l1 == NULL && l2 != NULL)
	{
		return l2;
	}

	if(l1->val < l2->val)
	{
		h = l1;
		l1 = l1->next;
		h->next = NULL;
	}
	else
	{
		h = l2;
		l2 = l2->next;
		h->next = NULL;
	}

	p = h;
	while(l1 != NULL && l2 != NULL)
	{
		if(l1->val < l2->val)
		{
			t = l1->next;
			p->next = l1;
			p = p->next;
			p->next = NULL;
			l1 = t;
		}
		else if(l1->val > l2->val)
		{
			t = l2->next;
			p->next = l2;
			p = p->next;
			p->next = NULL;
			l2 = t;
		}
		else
		{
			t = l1->next;
			p->next = l1;
			p = p->next;
			p->next = NULL;
			l1 = t;

			t = l2->next;
			p->next = l2;
			p = p->next;
			p->next = NULL;
			l2 = t;
		}
	}

	if(l1 != NULL)
	{
		p->next = l1;
	}

	if(l2 != NULL)
	{
		p->next = l2;
	}

	return h;
}

/*****************************************************************************
 * 24:Swap Nodes in Pairs
 * Given a linked list, swap every two adjacent nodes and return its head.
 *
 * For example,
 * Given 1->2->3->4, you should return the list as 2->1->4->3.
 * Your algorithm should use only constant space. You may not modify the
 * values in the list, only nodes itself can be changed.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/swap-nodes-in-pairs/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 * struct ListNode* swapPairs(struct ListNode* head) {
 *
 * }
 ****************************************************************************/
 struct ListNode* swapPairs(struct ListNode* head)
{
	struct ListNode* p = NULL;
	struct ListNode* t = NULL;
	struct ListNode* tail = NULL;

	if(head == NULL) return head;
	if(head->next == NULL) return head;

	tail = head;
	p = head->next->next;
	head = head->next;
	head->next = tail;
	tail->next = NULL;
	while(p != NULL)
	{
		if(p->next == NULL)
		{
			tail->next = p;
			break; /* odd number */
		}
		t = p->next->next;
		tail->next = p->next;
		p->next->next = p;
		tail = p;
		tail->next = NULL;
		p = t;
	}

	return head;
}

/*****************************************************************************
 * 26: Remove Duplicates from Sorted Array
 * Given a sorted array, remove the duplicates in place such that each element
 * appear only once and return the new length.
 * Do not allocate extra space for another array, you must do this in place
 * with constant memory.
 * For example,
 * Given input array A = [1,1,2],
 * Your function should return length = 2, and A is now [1,2].
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
 *
 * Code:
 * int removeDuplicates(int* nums, int numsSize) {
 * };
 ****************************************************************************/
int removeDuplicates(int nums[], int numsSize)
{
	int i = 0;
	int j = 0;

	if((nums == NULL) || (numsSize == 0)) return 0;

	while(j < numsSize)
	{
		while((nums[i] == nums[j]) && (j < numsSize))
		{
			j++;
		}
		i++;
		nums[i] = nums[j];
	}

	return i;
}

/*****************************************************************************
 * 27: Remove Element
 * Given an array and a value, remove all instances of that value in place and
 * return the new length.
 * The order of elements can be changed. It doesn't matter what you leave
 * beyond the new length.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/remove-element/
 *
 * Code:
 * int removeElement(int* nums, int numsSize, int val) {
 * }
 ****************************************************************************/
int removeElement(int* nums, int numsSize, int val)
{
	int i = 0;
	int j = 0;

	if((nums == NULL) || (numsSize == 0))
	{
		return 0;
	}

	while(i < numsSize)
	{
		if(nums[i] == val)
		{
			for(j = i; j < numsSize; j++)
			{
				nums[j] = nums[j + 1];
			}
			numsSize--;
			continue;
		}
		i++;
	}

	return numsSize;
}

/*****************************************************************************
 * 28: Implement strStr()
 * Returns the index of the first occurrence of needle in haystack, or -1 if
 * needle is not part of haystack.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/implement-strstr/
 *
 * Code:
 * int strStr(char *haystack, char *needle) {
 *
 * }
 *
 ****************************************************************************/
int strStr(char* haystack, char* needle)
{
	char* p1 = NULL;
	char* p2 = NULL;
	char* start = NULL;

	if((haystack == NULL) || (needle == NULL))
	{
		return -1;
	}

	if((*haystack == '\0') && (*needle == '\0'))
	{
		return 0;
	}

	if((*haystack != '\0') && (*needle == '\0'))
	{
		return 0;
	}

	if((*haystack == '\0') && (*needle != '\0'))
	{
		return -1;
	}

	p1 = haystack;
	p2 = needle;
	while((*p1 != '\0') && (*p2 != '\0'))
	{
		if(*p1 == *p2)
		{
			if(start == NULL) start = p1;
			p2++;
		}
		else
		{
			if(start != NULL)
			{
				p1 = start;
			}
			start = NULL;
			p2 = needle;
		}

		p1++;
	}

	if(*p2 == '\0')
	{
		return start - haystack;
	}
	else
	{
		return -1;
	}
}

/*****************************************************************************
 * 36: Valid Sudoku
 *
 * Determine if a Sudoku is valid, according to: [Sudoku Puzzles - The Rules.]
 * http://sudoku.com.au/TheRules.aspx:
 * There are just 3 rules to Sudoku.
 * (1).Each row must have the numbers 1-9 occuring just once.
 * (2).Each column must have the numbers 1-9 occuring just once.
 * (3).And the numbers 1-9 must occur just once in each of the 9 sub-boxes of 
 *     the grid.
 *
 * The Sudoku board could be partially filled, where empty cells are filled
 * with the character '.'.
 * A partially filled sudoku which is valid.
 * Note:
 * A valid Sudoku board (partially filled) is not necessarily solvable. Only
 * the filled cells need to be validated.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/valid-sudoku/
 *
 * Code:
 * bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
 *
 * }
 ****************************************************************************/
bool isValidSudoku(char** board, int boardRowSize, int boardColSize)
{
	int i = 0;
	int j = 0;
	int m = 0;
	int n = 0;
	int r = 0;
	int c = 0;
	char cell[9] = {0};

	if(board == NULL) return false;

	for(i = 0; i < boardRowSize; i++)
	{
		memset(cell, 0, sizeof(cell));
		for(j = 0; j < boardColSize; j++)
		{
			if((board[i][j] != '.') && (board[i][j] >= '1') && (board[i][j] <= '9'))
			{
				if(cell[board[i][j] - '0' - 1] != 0)
				{
					return false;
				}
				else
				{
					cell[board[i][j] - '0' - 1] = 1;
				}
			}
		}
	}

	for(i = 0; i < boardColSize; i++)
	{
		memset(cell, 0, sizeof(cell));
		for(j = 0; j < boardRowSize; j++)
		{
			if((board[j][i] != '.') && (board[j][i] >= '1') && (board[j][i] <= '9'))
			{
				if(cell[board[j][i] - '0' - 1] != 0)
				{
					return false;
				}
				else
				{
					cell[board[j][i] - '0' - 1] = 1;
				}
			}
		}
	}

	//行序号为(i - 1) / 3 *3 到(i - 1) / 3 *3+2
	//列序号为(i - 1)%3 *3 到(i - 1)%3 *3+2
	for(i = 0; i < boardRowSize; i++)
	{
		memset(cell, 0, sizeof(cell));
		for(m = 0; m < 3; m++)
		{
			for(n = 0; n < 3; n++)
			{
				r = (i - 1) / 3 * 3 + m;
				c = (i - 1) % 3 * 3 + n;
				if((board[r][c] != '.') && (board[r][c] >= '1') && (board[r][c] <= '9'))
				{
					if(cell[board[r][c] - '0' - 1] != 0)
					{
						return false;
					}
					else
					{
						cell[board[r][c] - '0' - 1] = 1;
					}
				}
			}
		}
	}

	return true;
}

/*****************************************************************************
 * 38: Count and Say
 * The count-and-say sequence is the sequence of integers beginning as follows:
 * 1, 11, 21, 1211, 111221, ...
 * 1 is read off as "one 1" or 11.
 * 11 is read off as "two 1s" or 21.
 * 21 is read off as "one 2, then one 1" or 1211.
 * Given an integer n, generate the nth sequence.
 * Note: The sequence of integers will be represented as a string.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/count-and-say/
 *
 * Code:
 * char* countAndSay(int n) {
 * }
 *
 * 题意是n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1
 * 个1，所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于
 * 上次字符串是21，有1个2和1个1，所以输出1211。依次类推
 *
 * 以下的实现n有限制.n太大会有内存溢出的死机故障.(现在估计n能达到30)
 ****************************************************************************/
char* countAndSay(int n)
{
	static char _038_say[1024 * 4] = {0};
	static char _038_say2[1024 * 4] = {0};
	char* p = NULL;
	char* t = NULL;
	int i = 0;
	int offset = 0;
	char current = 0;
	int num = 0;

	_038_say[0] = '1';
	_038_say[1] = 0;

	for(i = 1; i < n; i++)
	{
		p = _038_say;
		t = _038_say2;
		while(*p)
		{
			current = *p;
			num = 0;
			while(current == *p)
			{
				num++;
				p++;
			}
			offset = sprintf(t, "%d%d", num, current - '0');
			t += offset;
		}
		strcpy(_038_say, _038_say2);
	}

	return _038_say;
}

/*****************************************************************************
 * 58: Length of Last Word
 * Given a string s consists of upper/lower-case alphabets and empty space
 * characters ' ', return the length of last word in the string.
 * If the last word does not exist, return 0.
 * Note: A word is defined as a character sequence consists of non-space
 * characters only.
 * For example, Given s = "Hello World", return 5.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/length-of-last-word/
 *
 * Code:
 * int lengthOfLastWord(char* s) {
 *
 * }
 ****************************************************************************/
int lengthOfLastWord(char* s)
{
	int s_len = 0;
	char* p = NULL;

	if(s == NULL) return 0;

	p = s;
	while(*p){p++;}
	do{p--;}while((p > s) && (*p == ' '));
	while((p >= s) && (*p != ' ')){p--;s_len++;}
	return s_len;
}

/*****************************************************************************
 * 61: Rotate List
 * Given a list, rotate the list to the right by k places, where k is
 * non-negative.
 *
 * For example:Given 1->2->3->4->5->NULL and k = 2,return 4->5->1->2->3->NULL.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/tag/linked-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 * };
 * struct ListNode *rotateRight(struct ListNode *head, int k) {
 *
 * }
 *
 * Given [0,1,2] rotate 1 steps to right -> [2,0,1]
 * Given [0,1,2] rotate 2 steps to right -> [1,2,0]
 * Given [0,1,2] rotate 3 steps to right -> [0,1,2]
 * Given [0,1,2] rotate 4 steps to right -> [2,0,1]
 * 先求出链表的长度size,其实按着倒数第K%size个位置旋转,这个位置即size-(K%size)
 * http://www.cnblogs.com/kaituorensheng/p/3647668.html
 ****************************************************************************/
struct ListNode* rotateRight(struct ListNode* head, int k)
{
#if 0
	ListNode* fast = NULL;
	ListNode* slow = NULL;
	ListNode* fast_prev = NULL;
	ListNode* slow_prev = NULL;
	int length = 0;

	if(head == NULL) return NULL;
	if(k <= 0) return head;
	if(head->next == NULL) return head;

	fast = head;
	while(fast != NULL)
	{
		fast = fast->next;
		length++;
	}

	k = k % length;

	fast = slow = head;
	while((fast != NULL) && (k > 0))
	{
		fast = fast->next;
		k--;
	}

	while(fast != NULL)
	{
		fast_prev = fast;
		fast = fast->next;
		slow_prev = slow;
		slow = slow->next;
	}

	if(slow_prev != NULL)
	{
		slow_prev->next = NULL;
	}
	if(fast_prev != NULL)
	{
		fast_prev->next = head;
	}
	return slow;
#else
	int i = 0;
	if(head == NULL || head->next == NULL || k == 0)
	{
		return head;
	}

	int length = 0;
	struct ListNode *ptr = head, *tail = head;
	while (ptr != NULL) {
		length++;
		tail = ptr;
		ptr = ptr->next;
	}
	k %= length;

	ptr = head;
	for(i = 0; i < length - k - 1; i++) {
		ptr = ptr-> next;
	}

	tail->next = head;
	head = ptr->next;
	ptr->next = NULL;

	return head;
#endif
}

/*****************************************************************************
 * 66: Plus One
 * Given a non-negative number represented as an array of digits, plus one to
 * the number.
 * The digits are stored such that the most significant digit is at the head
 * of the list.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/plus-one/
 *
 * Code:
 * int* plusOne(int* digits, int digitsSize, int* returnSize) {
 *
 * }
 ****************************************************************************/
int* plusOne(int* digits, int digitsSize, int* returnSize)
{
	int i = 0;
	int val = 0;
	int carray = 1;

	if((digits == NULL) || (digitsSize == 0) || (returnSize == NULL))
	{
		return NULL;
	}

	for(i = 0; i < digitsSize; i++)
	{
		if(digits[i] != 9)
		{
			break;
		}
	}

	if(i == digitsSize)
	{
		*returnSize = digitsSize + 1;
		for(i = digitsSize - 1; i >= 0; i--)
		{
			val = digits[i] + carray;
			carray = val / 10;
			val = val % 10;
			digits[i + 1] = val;
		}
		digits[0] = 1;
	}
	else
	{
		*returnSize = digitsSize;
		for(i = digitsSize - 1; i >= 0; i--)
		{
			val = digits[i] + carray;
			carray = val / 10;
			val = val % 10;
			digits[i] = val;
		}
	}

	return digits;
}

/*****************************************************************************
 * 67: Add Binary
 * Given two binary strings, return their sum (also a binary string).
 * For example, a = "11" b = "1" Return "100".
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/add-binary/
 *
 * Code:
 * char* addBinary(char* a, char* b) {
 * }
 ****************************************************************************/
char* addBinary(char* a, char* b)
{
	int a_len = 0;
	int b_len = 0;
	int carray = 0;
	int val = 0;
	char* ta = NULL; //tail of string a
	char* tb = NULL; //tail of string b
	char* sum = NULL;
	int sum_len = 0;

	if(a == NULL && b == NULL) return NULL;
	if(a == NULL && b != NULL) return b;
	if(a != NULL && b == NULL) return a;

	ta = a; while(*ta){ta++; a_len++;} ta--;
	tb = b; while(*tb){tb++; b_len++;} tb--;

	sum_len = a_len > b_len ? (a_len + 2) : (b_len + 2);

	sum = (char*)malloc(sum_len);
	if(sum == NULL)
	{
		return NULL;
	}

	sum[--sum_len] = 0;
	while((ta >= a) && (tb >= b))
	{
		val = carray + *ta - '0' + *tb - '0';
		carray = val / 2;
		val = val % 2;
		sum[--sum_len] = val + '0';
		ta--;
		tb--;
	}

	while(ta >= a)
	{
		val = carray + *ta - '0';
		carray = val / 2;
		val = val % 2;
		sum[--sum_len] = val + '0';
		ta--;
	}

	while(tb >= b)
	{
		val = carray + *tb - '0';
		carray = val / 2;
		val = val % 2;
		sum[--sum_len] = val + '0';
		tb--;
	}

	if(carray == 1)
	{
		sum[--sum_len] = '1';
	}

	return sum + sum_len;
}

/*****************************************************************************
 * 70: Climbing Stairs
 * You are climbing a stair case. It takes n steps to reach to the top.
 * Each time you can either climb 1 or 2 steps. In how many distinct ways can
 * you climb to the top?
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/climbing-stairs/
 *
 * Code:
 * int climbStairs(int n) {
 * }
 *
 * 思路：
 * （1）题意为有一个n阶的梯子，一次你只能上一个或两个台阶，求你有多少种上台阶
 * 的方法。这道题其实很简单，就看你能不能想到它和某一个挺有名数列之间的联系，
 * 其考察我们发现规律和对常见数学数列理解的能力。
 * （2）这里我们不妨列举，并从中发现规律：
 * 当n=1时，ways=1
 * 当n=2时，有[2] [1,1]两种情况，ways=2
 * 当n=3时，有[1,1,1] [1,2] [2,1]三种情况，ways=3
 * 当n=4时，有[1,1,1,1] [2,2] [1,1,2] [1,2,1] [2,1,1]五种情况，ways=5
 * 当n=5时，有[1,1,1,1,1] [2,2,1] [2,1,2] [1,2,2] [1,1,1,2] [1,1,2,1] 
 * [1,2,1,1] [2,1,1,1]八种情况，ways=8
 * （3）这样我想你一眼就能看出规律了，当n>3时，n对应的情况数字为n-1和n-2之和。
 * 此时，规律正好和斐波那契数列出现的规律对应。
 * （4）斐波拉切数列是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，其被
 * 以递归的方法定义：F0=0，F1=1，Fn=F(n-1) + F(n-2)（n>=2）
 ****************************************************************************/
int climbStairs(int n)
{
	int i = 0;
	int fn_1 = 1;
	int fn_2 = 1;
	int fn = 0;
	if(n <= 0) return 0;
	if(n == 1) return 1;

	for(i = 2; i <= n; i++)
	{
		fn = fn_1 + fn_2;
		fn_1 = fn_2;
		fn_2 = fn;
	}

	return fn;
}

/*****************************************************************************
 * 78: Subsets
 * Given a set of distinct integers, nums, return all possible subsets.
 * Note:
 * (1) Elements in a subset must be in non-descending order.
 * (2)The solution set must not contain duplicate subsets.
 * For example,
 * If nums = [1,2,3], a solution is:
 * [
 *   [3],
 *   [1],
 *   [2],
 *   [1,2,3],
 *   [1,3],
 *   [2,3],
 *   [1,2],
 *   []
 * ]
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/subsets/
 *
 * Code:
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, 
 * assume caller calls free().
 * int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize)
 * {
 * }
 ****************************************************************************/
static int subsets_compare(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}
int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize)
{
	int i = 0;
	int j = 0;
	int idx = 0;
	int size = 0;
	int max = 1 << numsSize;
	int* temp = NULL;
	int** result = NULL;
	int* column = NULL;

	if((nums == NULL) || (numsSize == 0) || (columnSizes == NULL) 
			|| (returnSize == NULL)) return NULL;

	result = (int**)malloc(sizeof(int*) * max);
	column = (int*)malloc(sizeof(int) * max);
	for(i = 0;i < max;i++)
	{
		temp = (int*)malloc(sizeof(int) * max);
		idx = 0;
		size = 0;
		j = i;
		while(j > 0)
		{
			if(j & 1)
			{
				temp[size++] = nums[idx];
			}
			idx++;
			j = j >> 1;
		}
		qsort(temp, size, sizeof(int), subsets_compare);
		result[i] = temp;
		column[i] = size;
	}

	*columnSizes = column;
	*returnSize = max;
	return result;
}
/*****************************************************************************
 * 82: Remove Duplicates from Sorted List II
 * Given a sorted linked list, delete all nodes that have duplicate numbers,
 * leaving only distinct numbers from the original list.
 *
 * For example,
 * Given 1->2->3->3->4->4->5, return 1->2->5.
 * Given 1->1->1->2->3, return 2->3.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/sort-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *      int val;
 *      ListNode *next;
 * };
 * struct ListNode *deleteDuplicates(struct ListNode *head) {
 *
 * }
 *
 * 解法: 从当前链表中剪下第一个节点,这样就分成两个链表.对第二个链表进行遍历,如
 * 果第二个链表的头元素等于第一个链表尾巴元素,则对第二个链表的元素执行删除操作
 * ,直到不等于第一个链表尾元素即可,同时删除第一个链表的尾巴,并把第二个链表的头
 * 元素,剪下来添加到第一个链表上.如果不等则把第二个链表的头元素剪下来添加到第
 * 一个链表的尾巴上,并移动第一个链表的尾巴.如此循环直至第二个链表为空
 *
 * 变量解释:
 * tail 第一个链表的尾巴
 * prev 第一个链表尾巴的前驱
 * curr 第二个链表的头(当前待处理的节点)
 * next 第二个链表头的后继
 ****************************************************************************/
struct ListNode* deleteDuplicatesII(struct ListNode* head)
{
	struct ListNode* prev = NULL;
	struct ListNode* next = NULL;
	struct ListNode* tail = NULL;
	struct ListNode* curr = NULL;

	if(head == NULL) return head;

	curr = head->next;
	head->next = NULL;
	tail = head;

	while(curr != NULL)
	{
		next = curr->next;
		if(tail->val == curr->val)
		{
			while((curr != NULL) && (curr->val == tail->val))
			{
				next = curr->next;
				free(curr);
				curr = next;
			}

			if(curr != NULL)
			{
				next = curr->next;
				curr->next = NULL;
			}

			if(prev == NULL)
			{
				free(tail);
				head = tail = curr;
			}
			else
			{
				prev->next = curr;
				free(tail);
				tail = curr;
			}
		}
		else
		{
			curr->next = NULL;
			prev = tail;
			tail->next = curr;
			tail = tail->next;
		}
		curr = next;
	}

	return head;
}

/*****************************************************************************
 * 83: Remove Duplicates from Sorted List
 * Given a sorted linked list, delete all duplicates such that each element
 * appear only once.
 *
 * For example,
 * Given 1->1->2, return 1->2.
 * Given 1->1->2->3->3, return 1->2->3.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 * };
 * struct ListNode *deleteDuplicates(struct ListNode *head) {
 *
 * }
 ****************************************************************************/
struct ListNode* deleteDuplicates(struct ListNode* head)
{
	struct ListNode* fast = NULL;
	struct ListNode* slow = NULL;
	struct ListNode* next = NULL;

	if(head == NULL) return NULL;

	slow = head;
	fast = slow->next;
	while((fast != NULL) && (slow != NULL))
	{
		while((fast != NULL) && (fast->val == slow->val))
		{
			next = fast->next;
			free(fast);
			fast = next;
		}

		slow->next = fast;
		if(fast != NULL) fast = fast->next;
		slow = slow->next;
	}

	return head;
}

/*****************************************************************************
 * 86: Partition List
 * Given a linked list and a value x, partition it such that all nodes less
 * than x come before nodes greater than or equal to x.
 * You should preserve the original relative order of the nodes in each of
 * the two partitions.
 * For example,
 * Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/partition-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 * };
 * struct ListNode *partition(struct ListNode *head, int x) {
 *
 * }
 *
 * 解法:
 * 从头开始扫描单链表,如果遇到>x的节点,剪断单链表,变成两个单链表,记下第一个单
 * 链表的尾巴.从第二个单链表开始扫描,遇到<=x的节点,剪下来接到第一个单链表的尾
 * 巴,直至第二个单链表扫描完成.然后将第一个单链表与第二个单链表拼接.
 ****************************************************************************/
struct ListNode* partition(struct ListNode* head, int x)
{
	struct ListNode* tail = NULL;
	struct ListNode* curr = NULL;
	struct ListNode* next = NULL;
	struct ListNode* prev = NULL;
	struct ListNode* second = NULL;

	if(head == NULL) return head;

	curr = head;
	while((curr != NULL) && (curr->val < x))
	{
		tail = curr;
		curr = curr->next;
	}

	if(curr == NULL)
	{
		return head;
	}

	second = curr;
	prev = curr;
	curr = curr->next;
	while(curr != NULL)
	{
		next = curr->next;
		if(curr->val < x)
		{
			prev->next = curr->next;
			curr->next = NULL;
			if(tail != NULL)
			{
				tail->next = curr;
				tail = tail->next;
			}
			else
			{
				tail = curr;
				head = tail;
			}
		}
		else
		{
			prev = curr;
		}
		curr = next;
	}

	if(tail != NULL)
	{
		tail->next = second;
	}

	return head;
}

/*****************************************************************************
 * 88: Merge Sorted Array
 * Given two sorted integer arrays A and B, merge B into A as one sorted array.
 *
 * Note:
 * You may assume that A has enough space (size that is greater or equal to
 * m + n) to hold additional elements from B. The number of elements
 * initialized in A and B are m and n respectively.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/merge-sorted-array/
 *
 * Code:
 * void merge(int* nums1, int m, int* nums2, int n) {
 * }
 *
 * 解法:不用额外的存储空间
 * 示例1:A[1,2,4,5,*,*,*]; B[3]
 * 调用方法:A,4,B,1
 * 第一轮循环:A[1,2,4,5,5]
 * 第二轮循环:A[1,2,4,4,5]
 * 第三轮循环:A[1,2,3,4,5]
 * 从尾巴上开始存放,不会破坏A数组的原来的数据,把数据重新按有序的方法从尾端开始
 * 排放.
 ****************************************************************************/
void merge(int* nums1, int m, int* nums2, int n)
{
	int ia = 0;
	int ib = 0;
	int ic = 0;

	if((nums1 == NULL) || (nums2 == NULL)) return;
	if(n == 0) return;

	ia = m - 1;
	ib = n - 1;
	ic = m + n - 1;

	while((ia >= 0) && (ib >= 0))
	{
		if(nums1[ia] > nums2[ib])
		{
			nums1[ic--] = nums1[ia--];
		}
		else
		{
			nums1[ic--] = nums2[ib--];
		}
	}

	for(ic = 0; ic <= ib; ic++)
	{
		nums1[ic] = nums2[ic];
	}
}

/*****************************************************************************
 * 92: Reverse Linked List II
 * Reverse a linked list from position m to n. Do it in-place and in one-pass.
 *
 * For example:
 * Given 1->2->3->4->5->NULL, m = 2 and n = 4,
 * return 1->4->3->2->5->NULL.
 *
 * Note:
 * Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/reverse-linked-list-ii/
 *
 * Code:
 *
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 * };
 * struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
 * }
 *
 * 解法:
 *      |-------------|
 *                    V
 * 头---尾   尾---头   头---尾
 *               ^
 *      |________|
 * 从链表头往后数m个节点,然后把接下来的m-n+1个节点反序,然后再把剩下的接上.
 ****************************************************************************/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n)
{
	struct ListNode* curr = NULL;
	struct ListNode* prev = NULL;
	struct ListNode* next = NULL;
	struct ListNode* tail1 = NULL;
	struct ListNode* tail2 = NULL;

	if(head == NULL) return head;
	if((m <= 0) || (n <= 0) || (m > n)) return NULL;
	if(head->next == NULL) return head;
	if(m == n) return head;

	n = n - m;
	m = m - 1;
	for(curr = head; (m > 0) && (curr != NULL); m--)
	{
		prev = curr;
		curr = curr->next;
	}

	tail2 = curr;
	tail1 = prev;

	prev = curr;
	curr = curr->next;
	while((curr != NULL) && (n-- > 0))
	{
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}
	if(tail2 != NULL)
	{
		tail2->next = curr;
	}
	if(tail1 != NULL)
	{
		tail1->next = prev;
	}
	else
	{
		head = prev;
	}

	return head;
}

/*****************************************************************************
 * 94: Binary Tree Inorder Traversal
 * Given a binary tree, return the inorder traversal of its nodes' values.
 * For example: Given binary tree {1,#,2,3},
 *    1
 *     \
 *      2
 *     /
 *    3
 * return [1,3,2].
 *
 * Note: Recursive solution is trivial, could you do it iteratively?
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 * int* inorderTraversal(struct TreeNode* root, int* returnSize) {
 * 
 * }
 ****************************************************************************/
static void inorder(struct TreeNode* root, int* list, int* index)
{
	if(root == NULL) return;

	inorder(root->left, list, index);
	list[*index] = root->val;
	*index += 1;
	inorder(root->right, list, index);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
	int* l = NULL;
	int index = 0;

	if((root == NULL) || (returnSize == NULL)) return NULL;
	TreeGetNodesNumber(root, returnSize);

	l = (int*)malloc(sizeof(int) * (*returnSize));
	inorder(root, l, &index);
	return l;
}

/*****************************************************************************
 * 98: Validate Binary Search Tree
 * Given a binary tree, determine if it is a valid binary search tree (BST).
 * Assume a BST is defined as follows:
 * (1)The left subtree of a node contains only nodes with keys less than the
 * node's key.
 * (2)The right subtree of a node contains only nodes with keys greater than
 * the node's key.
 * (3)Both the left and right subtrees must also be binary search trees.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/validate-binary-search-tree/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 * bool isValidBST(struct TreeNode *root) {
 * }
 * };
 * 二叉搜索树定义为或者是一棵空树，或者是具有下列性质的二叉树:若它的左子树
 * 不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右
 * 子树上所有结点的值均大于它的根结点的值:它的左、右子树也分别为二叉排序树。
 * 递归判断，递归时传入两个参数，一个是左界，一个是右界，节点的值必须在两个界
 * 的中间，同时在判断做子树和右子树时更新左右界。
 * 在http://blog.csdn.net/longhopefor/article/details/25687119有个说明.
 * 用栈的解法:
 * bool isValidBST(struct TreeNode* root)
 * {
 * 	Stack* s = NULL;
 * 	struct TreeNode* p = NULL;
 * 	int64_t last_val = INT64_MIN;
 * 	bool status = true;
 * 
 * 	if(root == NULL) return true;

 * 	s = StackNew();

 * 	p = root;
 * 	while((p != NULL) || (!StackIsEmpty(s)))
 * 	{
 * 		while(p != NULL)
 * 		{
 * 			StackPush(s, p);
 * 			p = p->left;
 * 		}

 * 		if(!StackIsEmpty(s))
 * 		{
 * 			p = StackPop(s);
 * 			if(p->val <= last_val)
 * 			{
 * 				status = false;
 * 				break;
 * 			}
 * 			last_val = p->val;
 * 			p = p->right;
 * 		}
 * 	}
 * 	StackDestroy(s);
 * 	return status;
 * }
 ****************************************************************************/
static bool IsBST(struct TreeNode* root, int64_t left, int64_t right) 
{
	if(root == NULL)
	{
		return true;
	}
	 
	return (left < root->val) && (root->val < right) 
		&& IsBST(root->left, left, root->val) 
		&& IsBST(root->right, root->val, right);
}

bool isValidBST(struct TreeNode* root)
{
    return IsBST(root, INT64_MIN, INT64_MAX);
}

/*****************************************************************************
 * 100:Same Tree
 * Given two binary trees, write a function to check if they are equal or not.
 * Two binary trees are considered equal if they are structurally identical
 * and the nodes have the same value.
 *
 * Difficulty: Easy
 *
 * Link:https://oj.leetcode.com/problems/same-tree/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 * bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
 *
 * }
 ****************************************************************************/
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
	if((p == NULL) && (q == NULL)) return true;
	if((p == NULL) || (q == NULL)) return false;

	if((p->val == q->val) 
		&& isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
	{
		return true;
	}
	else
	{
		return false;
	}
}

/*****************************************************************************
 * 101:Symmetric Tree
 * Given a binary tree, check whether it is a mirror of itself (ie, symmetric
 * around its center).
 * For example, this binary tree is symmetric:
 * 	   1
 *    / \
 *   2   2
 *  / \ / \
 * 3  4 4  3
 * But the following is not:
 * 	   1
 *    / \
 *   2   2
 *    \   \
 *    3    3
 * Note: Bonus points if you could solve it both recursively and iteratively.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/symmetric-tree/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 * bool isSymmetric(struct TreeNode *root) {
 *
 * }
 *原来用队列,列表的解法,非递归
bool leetcode_101_is_symmetric(TreeNode* root)
{
	dlist_t* array = NULL;
	queue_t* q = NULL;
	queue_t* q2 = NULL;
	queue_t* temp = NULL;
	TreeNode* p = NULL;
	TreeNode* p2 = NULL;
	bool status = true;
	int index = 0;
	int size = 0;

	if(root == NULL) return true;

	q = lbe_queue_dlist_new(NULL);
	q2 = lbe_queue_dlist_new(NULL);
	array = lbe_dlist_new(NULL);

	lbe_queue_push(q, root);
	while(!lbe_queue_is_empty(q) && (status == true))
	{
		while(!lbe_queue_is_empty(q))
		{
			p = lbe_queue_pop0(q);
			if(p != NULL)
			{
				if(p->left != NULL) lbe_queue_push(q2, p->left);
				if(p->right != NULL) lbe_queue_push(q2, p->right);
				lbe_dlist_append(array, p->left);
				lbe_dlist_append(array, p->right);
			}
			else
			{
				lbe_dlist_append(array, NULL);
				lbe_dlist_append(array, NULL);
			}
		}

		size = lbe_dlist_size(array);
		if(size % 2 != 0)
		{
			status = false;
			break;
		}

		for(index = 0; index < size / 2; index++)
		{
			lbe_dlist_get(array, index, (void**)&p);
			lbe_dlist_get(array, size - index - 1, (void**)&p2);

			if(((p == NULL) && (p2 != NULL)) || ((p != NULL) && (p2 == NULL)))
			{
				status = false;
				break;
			}
			if((p != NULL) && (p2 != NULL) && (p->val != p2->val))
			{
				status = false;
				break;
			}
		}

		lbe_dlist_clear(array);
		temp = q2;
		q2 = q;
		q = temp;
	}

	lbe_queue_free(q);
	lbe_queue_free(q2);

	return status;
}
 ****************************************************************************/
static bool isSubtreeSymmetric(struct TreeNode* p, struct TreeNode* q)
{
	 if((p == NULL) && (q == NULL)) return true;
	 if((p == NULL) || (q == NULL)) return false;
     return (p->val == q->val) 
		 && isSubtreeSymmetric(q->left, p->right) 
		 && isSubtreeSymmetric(q->right, p->left);  
}

bool isSymmetric(struct TreeNode* root)
{
	if(root == NULL) return true;

	return isSubtreeSymmetric(root->left, root->right);
}

/*****************************************************************************
 * 102:Binary Tree Level Order Traversal
 * Given a binary tree, return the level order traversal of its nodes' values.
 * (ie, from left to right, level by level).
 * For example: Given binary tree {3,9,20,#,#,15,7},
 * 	  3
 *   / \
 *  9  20
 *  /   \
 * 15    7
 * return its level order traversal as:
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume 
 * caller calls free().
 * int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize)
 * {
 * }
 ****************************************************************************/
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize)
{
	int** vector = NULL;
	Queue* q1 = NULL;
	Queue* q2 = NULL;
	Queue* temp = NULL;
	struct TreeNode* p = NULL;
	int height = 0;
	int index = 0;

	if((root == NULL) || (columnSizes == NULL) || (returnSize == NULL))
	{
		return NULL;
	}

	*returnSize = TreeHeight(root) + 1;
	vector = (int**)malloc(sizeof(int*) * (*returnSize));
	if(vector == NULL)
	{
		return NULL;
	}
	*columnSizes = (int*)malloc(sizeof(int) * (*returnSize));
	if(*columnSizes == NULL)
	{
		free(vector);
		return NULL;
	}

	q1 = QueueNew();
	q2 = QueueNew();

	QueuePush(q1, root);
	while(!QueueIsEmpty(q1))
	{
		(*columnSizes)[height] = QueueSize(q1);
		vector[height] = (int*)malloc(sizeof(int) * ((*columnSizes)[height]));
		
		while(!QueueIsEmpty(q1))
		{
			p = QueuePop(q1);
			vector[height][index++] = p->val;
			if(p->left != NULL)
			{
				QueuePush(q2, p->left);
			}
			if(p->right != NULL)
			{
				QueuePush(q2, p->right);
			}
		}
		temp = q2;
		q2 = q1;
		q1 = temp;
		height++;
		index = 0;
	}

	QueueDestroy(q1);
	QueueDestroy(q2);
	return vector;
}

/*****************************************************************************
 * 104:Maximum Depth of Binary Tree
 * Given a binary tree, find its maximum depth.
 * The maximum depth is the number of nodes along the longest path from the
 * root node down to the farthest leaf node.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/maximum-depth-of-binary-tree/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *    int val;
 *    TreeNode *left;
 *    TreeNode *right;
 * };
 * int maxDepth(struct TreeNode *root) {
 * }
 ****************************************************************************/
int maxDepth(TreeNode* root)
{
	int left_depth = 0;
	int right_depth = 0;

	if(root == NULL) return 0;
	if((root->left == NULL) && (root->right == NULL)) return 1;

	left_depth = maxDepth(root->left) + 1;
	right_depth = maxDepth(root->right) + 1;
	return left_depth > right_depth ? left_depth : right_depth;
}

/*****************************************************************************
 * 107: Binary Tree Level Order Traversal II
 * Given a binary tree, return the bottom-up level order traversal of its
 * nodes' values. (ie, from left to right, level by level from leaf to root).
 * For example:
 * Given binary tree {3,9,20,#,#,15,7},
 *    3
 *   / \
 *  9  20
 *  /   \
 * 15    7
 * return its bottom-up level order traversal as:
 * [
 *   [15,7],
 *   [9,20],
 *   [3]
 * ]
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 * };
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *columnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume 
 * caller calls free().
 * int** levelOrderBottom(struct TreeNode* root, int** columnSizes, 
 * 	int* returnSize) {
 *
 * }
*****************************************************************************/
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize)
{
	int** vector = NULL;
	Queue* q = NULL;
	Queue* q2 = NULL;
	Queue* q3 = NULL;
	Queue* temp = NULL;
	Stack* s = NULL;
	struct TreeNode* p = NULL;
	int height = 0;
	int index = 0;

	if((root == NULL) || (columnSizes == NULL) || (returnSize == NULL))
	{
		return NULL;
	}

	*returnSize = TreeHeight(root) + 1;
	*returnSize = TreeHeight(root) + 1;
	vector = (int**)malloc(sizeof(int*) * (*returnSize));
	if(vector == NULL)
	{
		return NULL;
	}
	*columnSizes = (int*)malloc(sizeof(int) * (*returnSize));
	if(*columnSizes == NULL)
	{
		free(vector);
		return NULL;
	}

	q = QueueNew();
	q2 = QueueNew();
	q3 = QueueNew();
	s = StackNew();

	QueuePush(q3, root);
	StackPush(s, q3);
	QueuePush(q, root);
	while(!QueueIsEmpty(q))
	{
		q3 = QueueNew();
		while(!QueueIsEmpty(q))
		{
			p = QueuePop(q);
			if(p->left != NULL)
			{
				QueuePush(q2, p->left);
				QueuePush(q3, p->left);
			}
			if(p->right != NULL)
			{
				QueuePush(q2, p->right);
				QueuePush(q3, p->right);
			}
		}

		if(!QueueIsEmpty(q3))
		{
			StackPush(s, q3);
		}
		else
		{
			QueueDestroy(q3);
		}
		temp = q2;
		q2 = q;
		q = temp;
	}

	while(!StackIsEmpty(s))
	{
		temp = StackPop(s);
		(*columnSizes)[height] = QueueSize(temp);
		vector[height] = (int*)malloc(sizeof(int) * ((*columnSizes)[height]));
		while(!QueueIsEmpty(temp))
		{
			p = QueuePop(temp);
			vector[height][index++] = p->val;
		}
		index = 0;
		height++;
		QueueDestroy(temp);
	}

	QueueDestroy(q);
	QueueDestroy(q2);
	StackDestroy(s);

	return vector;
}

/*****************************************************************************
 * 110: Balanced Binary Tree
 * Given a binary tree, determine if it is height-balanced.
 * For this problem, a height-balanced binary tree is defined as a binary
 * tree in which the depth of the two subtrees of every node never differ
 * by more than 1.
 *
 * Difficulty: Easy
 *
 * Link:https://oj.leetcode.com/problems/balanced-binary-tree/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * class Solution {
 * public:
 * bool isBalanced(TreeNode *root) {
 *
 * }
 * };
 ****************************************************************************/
bool leetcode_110_is_balanced(TreeNode* root)
{
	if(root == NULL) return true;
	return leetcode_110_is_balanced(root->left)
			&& leetcode_110_is_balanced(root->right);
}

/*****************************************************************************
 * 111:Minimum Depth of Binary Tree
 * Given a binary tree, find its minimum depth.
 * The minimum depth is the number of nodes along the shortest path from the
 * root node down to the nearest leaf node.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * class Solution {
 * public:
 * int minDepth(TreeNode *root) {
 *
 * }
 * };
 ****************************************************************************/
int leetcode_111_min_depth(TreeNode* root)
{
	int left_depth = 0;
	int right_depth = 0;

	if(root == NULL) return 0;
	if((root->left == NULL) && (root->right == NULL)) return 1;

	if((root->left == NULL) && (root->right != NULL))
	{
		return 1 + leetcode_111_min_depth(root->right);
	}
	if((root->left != NULL) && (root->right == NULL))
	{
		return 1 + leetcode_111_min_depth(root->left);
	}

	left_depth = leetcode_111_min_depth(root->left) + 1;
	right_depth = leetcode_111_min_depth(root->right) + 1;
	return left_depth > right_depth ? right_depth : left_depth;
}

/*****************************************************************************
 * 112: Path Sum
 * Given a binary tree and a sum, determine if the tree has a root-to-leaf
 * path such that adding up all the values along the path equals the given
 * sum.
 *
 * For example:
 * Given the below binary tree and sum = 22,
 * 			  5
 * 			 / \
 * 			4   8
 * 		   /   / \
 * 		  11  13  4
 * 		 /  \      \
 * 		7    2      1
 * return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/path-sum/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 *
 * class Solution {
 *	public:
 *		bool hasPathSum(TreeNode *root, int sum) {
 *		}
 * };
 ****************************************************************************/
bool leetcode_112_has_path_sum(TreeNode* root, int sum)
{
	if(root == NULL) return false;
	if((root->left == NULL) && (root->right == NULL) && ((sum- root->val) == 0)) return true;
	return leetcode_112_has_path_sum(root->left, sum - root->val) ||
			leetcode_112_has_path_sum(root->right, sum - root->val);
}

/*****************************************************************************
 * 114:Flatten Binary Tree to Linked List
 * Given a binary tree, flatten it to a linked list in-place.
 * For example,
 * Given
 * 		 1
 * 		/ \
 * 	   2   5
 * 	  / \   \
 * 	 3   4   6
 * The flattened tree should look like:
 * 1
 * 	\
 * 	 2
 * 	  \
 * 	   3
 * 		\
 * 		 4
 * 		  \
 * 		   5
 * 			\
 * 			 6
 * Hints: If you notice carefully in the flattened tree, each node's right
 * child points to the next node of a pre-order traversal.
 *
 * Difficulty: Medium
 *
 * Link:https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * class Solution {
 * public:
 * void flatten(TreeNode *root) {
 *
 * }
 * };
 ****************************************************************************/
void leetcode_114_flatten(TreeNode* root)
{
#if 0
	stack_t* s = NULL;
	TreeNode* p = NULL;
	TreeNode* q = NULL;

	if(root == NULL) return;

	s = lbe_stack_dlist_new(NULL);
	lbe_stack_push(s, root);
	while(!lbe_stack_is_empty(s))
	{
		p = lbe_stack_pop0(s);
		if(p->right != NULL) lbe_stack_push(s, p->right);
		if(p->left != NULL) lbe_stack_push(s, p->left);
		p->left = p->right = NULL;
		if(q == NULL)
		{
			q = p;
		}
		else
		{
			q->right = p;
			q = q->right;
		}
	}

	lbe_stack_free(s);
#endif
}

/*****************************************************************************
 * 116: Populating Next Right Pointers in Each Node
 * Given a binary tree
 * struct TreeLinkNode {
 *   TreeLinkNode *left;
 *   TreeLinkNode *right;
 *   TreeLinkNode *next;
 * }
 * Populate each next pointer to point to its next right node. If there is
 * no next right node, the next pointer should be set to NULL.
 * Initially, all next pointers are set to NULL.
 *
 * Note:
 * (1):You may only use constant extra space.
 * (2):You may assume that it is a perfect binary tree (ie, all leaves are
 * at the same level, and every parent has two children).
 *
 * For example,
 * Given the following perfect binary tree,
 * 		 1
 * 	   /  \
 * 	  2    3
 * 	 / \  / \
 * 	4  5  6  7
 * After calling your function, the tree should look like:
 * 		 1 -> NULL
 * 	   /  \
 * 	  2 -> 3 -> NULL
 * 	 / \  / \
 * 	4->5->6->7 -> NULL
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
 *
 * Code:
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *   int val;
 *   TreeLinkNode *left, *right, *next;
 *   TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 * class Solution {
 * public:
 * void connect(TreeLinkNode *root) {
 *
 * }
 * };
 ****************************************************************************/
void leetcode_116_connect(TreeLinkNode* root)
{
#if 0
	queue_t* q1 = NULL;
	queue_t* q2 = NULL;
	queue_t* temp = NULL;
	TreeLinkNode* p1 = NULL;
	TreeLinkNode* p2 = NULL;

	if(root == NULL) return;

	q1 = lbe_queue_dlist_new(NULL);
	q2 = lbe_queue_dlist_new(NULL);

	lbe_queue_push(q1, root);
	while(!lbe_queue_is_empty(q1))
	{
		while(!lbe_queue_is_empty(q1))
		{
			p1 = lbe_queue_pop0(q1);
			if(p2 == NULL)
			{
				p2 = p1;
			}
			else
			{
				p2->next = p1;
				p2 = p2->next;
			}
			if(p1->left != NULL)
			{
				lbe_queue_push(q2, p1->left);
			}
			if(p1->right != NULL)
			{
				lbe_queue_push(q2, p1->right);
			}
		}
		p2 = NULL;
		temp = q2;
		q2 = q1;
		q1 = temp;
	}
	lbe_queue_free(q1);
	lbe_queue_free(q2);
#endif
}

/*****************************************************************************
 * 118:Pascal's Triangle
 * Given numRows, generate the first numRows of Pascal's triangle.
 * For example, given numRows = 5,Return
 * [
 *      [1],
 *     [1,1],
 *    [1,2,1],
 *   [1,3,3,1],
 *  [1,4,6,4,1]
 * ]
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/pascals-triangle/
 *
 * Code:
 * class Solution {
 * public:
 * vector<vector<int> > generate(int numRows) {
 * }
 * };
 ****************************************************************************/
#if 0
list_t* leetcode_118_generate(int num_rows)
{
	list_t* rows = NULL;
	list_t* row = NULL;
	list_t* last = NULL;
	int i = 0;
	int j = 0;
	int v1 = 0;
	int v2 = 0;

	rows = lbe_list_new((free_func_t)lbe_list_free);

	if(num_rows <= 0) return rows;

	for(i = 0; i < num_rows; i++)
	{
		row = lbe_list_new(NULL);
		lbe_list_append(row, (void*)1);
		for(j = 1; j <= i; j++)
		{
			if(j == i)
			{
				lbe_list_append(row, (void*)1);
			}
			else
			{
				lbe_list_get(last, j, (void**)&v1);
				lbe_list_get(last, j - 1, (void**)&v2);
				lbe_list_append(row, (void*)(v1 + v2));
			}
		}
		last = row;
		lbe_list_append(rows, row);
	}

	return rows;
}
#endif

/*****************************************************************************
 * 119: Pascal's Triangle II
 * Given an index k, return the kth row of the Pascal's triangle.
 * For example, given k = 3,
 * Return [1,3,3,1].
 * Note:
 * Could you optimize your algorithm to use only O(k) extra space?
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/pascals-triangle-ii/
 *
 * Code:
 * class Solution {
 * public:
 * vector<int> getRow(int rowIndex) {
 * }
 * };
 * 杨辉三角:
 * 前提：端点的数为1.
 * 1、每个数等于它上方两数之和。
 * 2、每行数字左右对称，由1开始逐渐变大。
 * 3、第n行的数字有n项。
 * 4、第n行数字和为2n-1。
 * 5、第n行的第m个数和第n-m+1个数相等，即C(n-1,m-1)=C(n-1,n-m)（组合数性质之一）
 * 6、每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数
 * 等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即C(n+1,i)=C(n,i)+C(n,i-1)
 * 7、第n行的m个数可表示为C(n-1,m-1)（n-1下标，m-1上标），即为从n-1个不同元素中取m-1
 * 个元素的组合数。（见右图）组合数计算方法：C(n,m)=n!/[m!(n-m)!]
 * 8、(a+b)^n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。
 * 9、将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第
 * 4n+1个斐波那契数；将第2n行第2个数(n>1)，跟第2n-1行第4个数、第2n-2行第6个数……这些数
 * 之和是第4n-2个斐波那契数。
 * 10、将各行数字相排列，可得11的n-1（n为行数）次方：1=11^0; 11=11^1; 121=11^2……;
 * 细心的人可能会发现当n≥5时会不符合这一条性质，其实是这样的：把第n行的最右面的数字"1"放在
 * 个位，然后把左面的一个数字的个位对齐到十位... ...，以此类推，把空位用“0”补齐，然后把所有
 * 的数加起来，得到的数正好是11的n-1次方。以n=11为例，第十一行的数为：
 * 1,10,45,120,210,252,210,120,45,10,1；
 *
 * 第n行的:
 * 第一个数为1，
 * 第二个数为1×(n-1)，
 * 第三个数为1×(n-1)×（n-2）/2，
 * 第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。
 *
 * k = 3(n=4), Return [1,3,3,1].
 * k = 4(n=5), Return [1,4,6,4,1]
 ****************************************************************************/
#if 0
list_t* leetcode_119_get_row(int row_index)
{
	int v1 = 0;
	int v2 = 0;
	int i = 0;
	int j = 0;
	list_t* l = NULL;

	if(row_index <= 0) return NULL;

	l = lbe_list_new(NULL);
	for(i = 0; i < (row_index + 1); i++)
	{
		lbe_list_append(l, (void*)1);
	}

	for(i = 1; i <= row_index; i++)
	{
		for(j = i; j > 0; j--)
		{
			if(j == i)
			{
				lbe_list_set(l, j, (void*)1);
			}
			else
			{
				lbe_list_get(l, j, (void**)&v1);
				lbe_list_get(l, j - 1, (void**)&v2);
				lbe_list_set(l, j, (void*)(v1 + v2));
			}
		}
	}

	return l;
}
#endif

/*****************************************************************************
 * 125: Valid Palindrome
 * Given a string, determine if it is a palindrome, considering only
 * alphanumeric characters and ignoring cases.
 * For example,
 * "A man, a plan, a canal: Panama" is a palindrome.
 * "race a car" is not a palindrome.
 * Note:
 * Have you consider that the string might be empty? This is a good question
 * to ask during an interview.
 * For the purpose of this problem, we define empty string as valid palindrome.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/valid-palindrome/
 *
 * Code:
 * class Solution {
 * public:
 * bool isPalindrome(string s) {
 * }
 * };
 ****************************************************************************/
bool leetcode_125_is_palindrome(char* p)
{
	//const char* p = s.c_str();
	const char* e = NULL;

	if(p == NULL) return false;
	if(*p == '\0') return true;

	e = p;
	while(*e) // move to end;
	{
		e++;
	}

	while(p <= e)
	{
		if(!isalnum(*p))
		{
			p++;
		}
		else if(!isalnum(*e))
		{
			e--;
		}
		else if(tolower(*p) == tolower(*e))
		{
			p++;
			e--;
		}
		else
		{
			return false;
		}
	}

	return true;
}

/*****************************************************************************
 * 136: Single Number
 * Given an array of integers, every element appears twice except for one.
 * Find that single one.
 * Note: Your algorithm should have a linear runtime complexity. Could you
 * implement it without using extra memory?
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/single-number/
 *
 * Code:
 * class Solution {
 * public:
 * int singleNumber(int A[], int n) {
 * }
 * };
 * 解法: http://www.cnblogs.com/changchengxiao/p/3413294.html
 * 对于异或来说：
 * 1. 异或运算是可交换，即 a ^ b = b ^ a
 * 2. 0 ^ a = a
 * 那么如果对所有元素做异或运算，其结果为那个出现一次的元素，理解是a1 ^ a2 ^ ....，可以将
 * 所有相同元素交换至相邻位置，首先运算相同元素，则会产生(n - 1)/2个0异或积，剩余一个单一
 * 元素，他们的异或积为这个单一元素自己，得解。
 * 本题扩展
 * 1.一个数组中有两个元素只出现一次，其他所有元素都出现两次，求这两个只出现一次的元素
 * [解题思路]
 * 将数组所有元素都进行异或得到一个不为0的结果，根据这个结果中的不为0的某一位将数组分成两组,
 * 将两组中的元素进行异或，如两个数组的异或值都不为0，则得到最后结果
 * 2.一个数组中有一个元素只出现1次，其他所有元素都出现k次，求这个只出现1次的元素
 * [解题思路]
 * 当k为偶数时，同lss,当k为奇数时，将数组中每个元素的每一位相加mod k，得到结果即位出现1次的
 * 元素，时间复杂度O(nlen)，空间复杂度为O(1)
 ****************************************************************************/
int leetcode_136_single_number(int A[], int n)
{
	int i = 0;
	int result = 0;

	if((A == NULL) || (n == 0)) return 0;
	if(n % 2 != 1) return 0;

	result = A[0];
	for(i = 1; i < n; i++)
	{
		result = result ^ A[i];
	}

	return result;
}

/*****************************************************************************
 * 137:Single Number II
 * Given an array of integers, every element appears three times except for
 * one. Find that single one.
 * Note: Your algorithm should have a linear runtime complexity. Could you
 * implement it without using extra memory?
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/single-number-ii/
 *
 * Code:
 * class Solution {
 * public:
 * int singleNumber(int A[], int n) {
 * }
 * };
 * 解法: http://blog.csdn.net/jiadebin890724/article/details/23306837
 * int数据共有32位，可以用32变量存储这N个元素中各个二进制位上1出现的次数，最后在进行模三操
 * 作，如果为1，那说明这一位是要找元素二进制表示中为1的那一位。时间：O(32*N)，这是一个通用
 * 的解法，如果把出现3次改为 k 次，那么只需模k就行了。
 ****************************************************************************/
int leetcode_137_signle_number_ii(int A[], int n)
{
	int i = 0;
	int j = 0;
	int bitnum[32] = {0};
	int res = 0;

	if((A == NULL) || (n == 0)) return 0;
	if(n % 3 != 1) return 0;

	for(i = 0; i < 32; i++){
		for(j = 0; j < n; j++){
			bitnum[i] += (A[j]>>i)&1;
		}
		res |= (bitnum[i] % 3) << i;
	}
	return res;
}

/*****************************************************************************
 * 141:Linked List Cycle
 * Given a linked list, determine if it has a cycle in it.
 *
 * Follow up: Can you solve it without using extra space?
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/linked-list-cycle/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * class Solution {
 * public:
 * bool hasCycle(ListNode *head) {
 *
 * }
 * };
 ****************************************************************************/
bool leetcode_141_has_cycle(ListNode* head)
{
	ListNode* fast = NULL;
	ListNode* slow = NULL;

	if(head == NULL) return false;
	if(head->next == head) return true;

	fast = slow = head;
	while((fast != NULL) && (fast->next != NULL))
	{
		slow = slow->next;
		fast = fast->next->next;
		if(slow == fast)
		{
			return true;
		}
	}

	return false;
}

/*****************************************************************************
 * 142:Linked List Cycle II
 * Given a linked list, return the node where the cycle begins. If there is
 * no cycle, return null.
 *
 * Follow up: can you solve it without using extra space
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/linked-list-cycle-ii/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * class Solution {
 * public:
 * ListNode *detectCycle(ListNode *head) {
 *
 * }
 * };
 *
 * Input:	{1}, no cycle
 * Output:	tail connects to node index 0
 * Expected:	no cycle
 *
 ****************************************************************************/
ListNode* leetcode_142_detect_cycle(ListNode* head)
{
	ListNode* fast = NULL;
	ListNode* slow = NULL;

	if(head == NULL) return NULL;
	if(head->next == NULL) return NULL;
	if(head->next == head) return head;

	slow = fast = head;
	while((fast != NULL) && (fast->next != NULL))
	{
		fast = fast->next->next;
		slow = slow->next;
		if(fast == slow)
		{
			break;
		}
	}

	if(fast != slow)
	{
		return NULL;
	}

	fast = head;
	while(fast != slow)
	{
		fast = fast->next;
		slow = slow->next;
	}

	return fast;
}

/*****************************************************************************
 * 143: Reorder List
 * Given a singly linked list L: L0→L1→…→Ln-1→Ln,
 * reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
 * You must do this in-place without altering the nodes' values.
 * For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/reorder-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * class Solution {
 * public:
 * void reorderList(ListNode *head) {
 *
 * }
 * };
 * 解法:
 * 先把链表的头剪下来,这样分成两个链表,循环遍历第二链表,第一次先剪下链表的尾巴接到第一个链表的
 * 尾巴,第二次剪下链表的头部,接到第一个链表的尾巴.直到第二个链表为空.
 * 递归解法的思想:
 * 从单链表中剪下头和尾巴,如果无法剪下或只剪下头或只剪下为尾巴,递归结束.
 * 前面的解法太耗时间,重新实现:
 * 把链表一分为二.然后把第二个链表反转.然后把第一个链表与第二个链表连接起来即可.
 * 对单链表遍历了O(n) + O(n/2) + O(n/2) + O(n/2) = 2n + n/2
 * 而第一种方法则遍历了, (n - 1) + (n - 2 - 1) + (n - 2 - 2 - 1) + ...
 ****************************************************************************/
void leetcode_143_reorder_list(ListNode* head)
{
#if 0
	ListNode* p = NULL;
	ListNode* tail = NULL;
	ListNode* t = NULL;
	ListNode* prev = NULL;

	if(head == NULL) return;

	p = head->next;
	head->next = NULL;
	tail = head;

	while(p != NULL)
	{
		t = p;
		while(t->next != NULL)
		{
			prev = t;
			t = t->next;
		}
		if(t == p)
		{
			tail->next = p;
			p = p->next;
			tail = tail->next;
			tail->next = NULL;
		}
		else
		{
			prev->next = NULL;
			tail->next = t;
			tail = tail->next;
			tail->next = p;
			tail = tail->next;
			p = p->next;
			tail->next = NULL;
		}
	}
#else
	ListNode* p1 = NULL; //first list
	ListNode* p2 = NULL; //second list
	ListNode* tail = NULL; //first list tail
	ListNode* prev = NULL;
	ListNode* next = NULL;
	ListNode* p1_next = NULL;
	ListNode* p2_next = NULL;

	if(head == NULL) return;

	p2 = p1 = head;
	while((p1 != NULL) && (p1->next != NULL))
	{
		p2 = p2->next;
		p1 = p1->next->next;
	}

	tail = p2;
	p2 = p2->next;
	tail->next = NULL;
	while(p2 != NULL)
	{
		next = p2->next;
		p2->next = prev;
		prev = p2;
		p2 = next;
	}

	p1 = head->next;
	head->next = NULL;
	tail = head;
	p2 = prev;

	while((p1 != NULL) && (p2 != NULL))
	{
		p1_next = p1->next;
		p2_next = p2->next;
		tail->next = p2;
		tail = tail->next;
		tail->next = p1;
		tail = tail->next;
		tail->next = NULL;
		p1 = p1_next;
		p2 = p2_next;
	}

	if(p1 != NULL)
	{
		tail->next = p1;
	}
#endif
}

/*****************************************************************************
 * 144: Binary Tree Preorder Traversal
 * Given a binary tree, return the preorder traversal of its nodes' values.
 * For example:
 * Given binary tree {1,#,2,3},
 *    1
 *     \
 * 	   2
 * 	  /
 *  3
 * return [1,2,3].
 * Note: Recursive solution is trivial, could you do it iteratively?
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/binary-tree-preorder-traversal/
 *
 * Code:
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 * class Solution {
 * public:
 * vector<int> preorderTraversal(TreeNode *root) {
 * }
 * };
 ****************************************************************************/
#if 0
list_t* leetcode_144_preorder_traversal(TreeNode* root)
{
	list_t* l = NULL;
	stack_t* s = NULL;
	TreeNode* p = NULL;

	if(root == NULL) return NULL;

	s = lbe_stack_dlist_new(NULL);
	l = lbe_list_new(NULL);

	lbe_stack_push(s, root);
	while(!lbe_stack_is_empty(s))
	{
		p = lbe_stack_pop0(s);
		lbe_list_append(l, (void*)p->val);
		if(p->right != NULL) lbe_stack_push(s, p->right);
		if(p->left != NULL) lbe_stack_push(s, p->left);
	}

	lbe_stack_free(s);

	return l;
}
#endif

/*****************************************************************************
 * 147: Insertion Sort List
 * Sort a linked list using insertion sort.
 *
 * Difficulty: Medium
 *
 * Link: https://oj.leetcode.com/problems/insertion-sort-list/
 *
 * Code:
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 * class Solution {
 * public:
 * ListNode *insertionSortList(ListNode *head) {
 *
 * }
 * };
 ****************************************************************************/
ListNode* leetcode_147_insertion_sort_list(ListNode* head)
{
	ListNode* sort = NULL;
	ListNode* prev = NULL;
	ListNode* p = NULL;
	ListNode* t = NULL;
	ListNode* next = NULL;

	if(head == NULL) return head;

	sort = head;
	p = head->next;
	sort->next = NULL;

	while(p != NULL)
	{
		next = p->next;
		p->next = NULL;
		t = sort;
		prev = NULL;
		while(t != NULL)
		{
			if(t->val > p->val)
			{
				break;
			}
			prev = t;
			t = t->next;
		}

		if(prev != NULL)
		{
			p->next = prev->next;
			prev->next = p;
		}
		else
		{
			p->next = sort;
			sort = p;
		}

		p = next;
	}

	return sort;
}

/*****************************************************************************
 * 155:Min Stack
 * Design a stack that supports push, pop, top, and retrieving the minimum
 * element in constant time.
 * push(x) -- Push element x onto stack.
 * pop() -- Removes the element on top of the stack.
 * top() -- Get the top element.
 * getMin() -- Retrieve the minimum element in the stack.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/min-stack/
 *
 * Code:
 * class MinStack {
 * public:
 * void push(int x) {
 * }
 *
 * void pop() {
 * }
 *
 * int top() {
 * }
 *
 * int getMin() {
 * }
 * };
 ****************************************************************************/
MinStack* leetcode_155_min_stack(void)
{
	//return MinStackNew();
}

/*****************************************************************************
 * 160:Intersection of Two Linked Lists
 * Write a program to find the node at which the intersection of two singly
 * linked lists begins.
 *
 * For example, the following two linked lists:
 * A:          a1 → a2
 * 				   ↘
 * 					 c1 → c2 → c3
 * 				   ↗
 * B:     b1 → b2 → b3
 * begin to intersect at node c1.
 *
 * Notes:
 * If the two linked lists have no intersection at all, return null.
 * The linked lists must retain their original structure after the function returns.
 * You may assume there are no cycles anywhere in the entire linked structure.
 * Your code should preferably run in O(n) time and use only O(1) memory.
 *
 * Difficulty: Easy
 *
 * Link:https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
 *
 * Code:
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
* class Solution {
* public:
* ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
*
* }
* };
 ****************************************************************************/
ListNode* leetcode_160_get_intersection_node(ListNode* headA, ListNode* headB)
{
	ListNode* pa = NULL;
	ListNode* pb = NULL;
	int la = 0;
	int lb = 0;
	int i = 0;

	if((headA == NULL) || (headB == NULL))
	{
		return NULL;
	}

	for(pa = headA; pa != NULL; pa = pa->next)
	{
		la++;
	}
	for(pb = headB; pb != NULL; pb = pb->next)
	{
		lb++;
	}
	if(pa != pb)
	{
		return NULL;
	}

	pa = headA;
	pb = headB;
	if(la > lb)
	{
		for(i = 0; i < (la - lb); i++)
		{
			pa = pa->next;
		}
	}
	else
	{
		for(i = 0; i < (lb - la); i++)
		{
			pb = pb->next;
		}
	}
	while(pa != NULL)
	{
		if(pa == pb)
		{
			break;
		}
		pa = pa->next;
		pb = pb->next;
	}

	return pa;
}

/*****************************************************************************
 * 165:Compare Version Numbers
 * Compare two version numbers version1 and version1.
 * If version1 > version2 return 1, if version1 < version2 return -1,
 * otherwise return 0.
 *
 * You may assume that the version strings are non-empty and contain only
 * digits and the . character. The . character does not represent a decimal
 * point and is used to separate number sequences. For instance, 2.5 is not
 * "two and a half" or "half way to version three", it is the fifth
 * second-level revision of the second first-level revision.
 *
 * Here is an example of version numbers ordering:
 * 0.1 < 1.1 < 1.2 < 13.37
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/compare-version-numbers/
 *
 * Code:
 *	class Solution {
 *	public:
 *		int compareVersion(string version1, string version2) {
 *
 *		}
 *	};
 *
 * Compile Error:
 * Line 9: no match for ‘operator==’ (operand types are ‘std::string
 * {aka std::basic_string<char>}’ and ‘long int’)
 * Compile Error:
 * Line 14: invalid conversion from ‘const char*’ to ‘char*’ [-fpermissive]
 * Wrong Answer, Input:	"1", "1.1" Output:	1 Expected:	-1
 ****************************************************************************/
int leetcode_165_compare_version(char* version1, char* version2)
{
	const char* p1 = NULL;
	const char* p2 = NULL;
	int v1 = 0;
	int v2 = 0;

	if((version1 == NULL) || (version2 == NULL))
	{
		return 0;
	}

	p1 = version1;
	p2 = version2;
	while((*p1 != '\0') || (*p2 != '\0'))
	{
		while((*p1 != '\0') && (*p1 != '.'))
		{
			v1 = v1 * 10 + (*p1 - '0');
			p1++;
		}

		while((*p2 != '\0') && (*p2 != '.'))
		{
			v2 = v2 * 10 + (*p2 - '0');
			p2++;
		}

		if(v1 < v2)
		{
			return -1;
		}
		else if(v1 > v2)
		{
			return 1;
		}
		else
		{
			v1 = 0;
			v2 = 0;
			if((*p1 == '\0') && (*p2 == '\0'))
			{
				return 0;
			}
			else if((*p1 == '\0') && (*p2 != '\0'))
			{
				p2++;
			}
			else if((*p1 != '\0') && (*p2 == '\0'))
			{
				p1++;
			}
			else
			{
				p1++;
				p2++;
			}
		}
	}

	return 0;
}

/*****************************************************************************
 * 168: Excel Sheet Column Title
 * Given a positive integer, return its corresponding column title as appear
 * in an Excel sheet.
 * For example:
 * 	1 -> A
 * 	2 -> B
 * 	3 -> C
 * 	...
 * 	26 -> Z
 * 	27 -> AA
 * 	28 -> AB
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/excel-sheet-column-title/
 *
 * Code:
 * class Solution {
 * public:
 * string convertToTitle(int n) {
 * }
 * };
 ****************************************************************************/
char* leetcode_168_convert_to_title(int n)
{
	static char _168_title[128] = {0};
	char temp = 0;
	unsigned int i = 0;
	unsigned int j = 0;
	int m = 0;

	if(n <= 0) return NULL;

	while((n > 0) && (i < (sizeof(_168_title) - 1)))
	{
		m = (n - 1) % 26;
		_168_title[i++] = 'A' + m;
		n = (n - 1) / 26;
	}
	_168_title[i] = '\0';
	while(j < i / 2)
	{
		temp = _168_title[j];
		_168_title[j] = _168_title[i - j - 1];
		_168_title[i - j - 1] = temp;
		j++;
	}

	//return string(_168_title);
	return _168_title;
}

/*****************************************************************************
 * 169: Majority Element
 * Given an array of size n, find the majority element. The majority element
 * is the element that appears more than ⌊ n/2 ⌋ times.
 * You may assume that the array is non-empty and the majority element always
 * exist in the array.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/majority-element/
 *
 * Code:
 * class Solution {
 * public:
 * int majorityElement(vector<int> &num) {
 * }
 * };
 ****************************************************************************/
int leetcode_169_majority_element(int num[], int n)
{
	int times = 0;
	int candidate = 0;
	int i = 0;

	for(i = 0; i < n; i ++)
	{
		if(times == 0)
		{
			candidate = num[i];
			times = 1;
		}
		else
		{
			if(candidate == num[i])
				times++;
			else
				times--;
		}
	}
	return candidate;
}

/*****************************************************************************
 * 170:Two Sum III - Data structure design
 * Design and implement a TwoSum class. It should support the following
 * operations:add and find.
 * add - Add the number to an internal data structure.
 * find - Find if there exists any pair of numbers which sum is equal to the
 * value.
 * For example,add(1); add(3); add(5);
 * find(4) -> true
 * find(7) -> false
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/two-sum-iii-data-structure-design/
 *
 * Code:
 * public class TwoSum {
 * public void add(int number) {
 * }
 * public boolean find(int value) {
 * }
 * }
 ****************************************************************************/
TwoSum* leetcode_170_two_sum(void)
{
	return TwoSumNew();
}

/*****************************************************************************
 * 171:Excel Sheet Column Number
 * Related to question Excel Sheet Column Title
 * Given a column title as appear in an Excel sheet, return its corresponding
 * column number.
 * For example:
 * 	A -> 1
 * 	B -> 2
 * 	C -> 3
 * 	...
 * 	Z -> 26
 * 	AA -> 27
 * 	AB -> 28
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/excel-sheet-column-number/
 *
 * Code:
 * class Solution {
 * public:
 * int titleToNumber(string s) {
 * }
 * };
 ****************************************************************************/
int leetcode_171_title_to_number(char* s)
{
	int n = 0;

	if(s == NULL) return 0;
	if(*s == '\0') return 0;

	while(*s != '\0')
	{
		if((*s >= 'A') && (*s <= 'Z'))
		{
			n = n * ('Z' - 'A' + 1) + (*s - 'A') + 1;
		}
		else
		{
			return 0;
		}
		s++;
	}

	return n;
}

/*****************************************************************************
 * 172:Factorial Trailing Zeroes
 * Given an integer n, return the number of trailing zeroes in n!.
 * Note: Your solution should be in logarithmic time complexity.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/factorial-trailing-zeroes/
 *
 * Code:
 * class Solution {
 * public:
 * int trailingZeroes(int n) {
 * }
 * };
 *
 * 解法:
 * 以下列出0至20的阶乘
 * 0=1注意(0的阶乘是存在的)
 * 1=1
 * 2=2
 * 3=6
 * 4=24
 * 5=120
 * 6=720
 * 7=5,040
 * 8=40,320
 * 9=362,880
 * 10=3,628,800
 * 11=39,916,800
 * 12=479,001,600
 * 13=6,227,020,800
 * 14=87,178,291,200
 * 15=1,307,674,368,000
 * 16=20,922,789,888,000
 * 17=355,687,428,096,000
 * 18=6,402,373,705,728,000
 * 19=121,645,100,408,832,000
 * 20=2,432,902,008,176,640,000
 * 另外数学家定义0=1所以0=1
 * 而当n≥5时n的个位数字都是0.
 ****************************************************************************/
int leetcode_172_trailing_zeroes(int n)
{
	int zeroes = 0;

	if(n < 5) return 0;
	while(n >= 5)
	{
		n = n / 5;
		zeroes += n;
	}

	return zeroes;
}

/*****************************************************************************
 * 179:Largest Number
 * Given a list of non negative integers, arrange them such that they form
 * the largest number.
 * For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
 * Note: The result may be very large, so you need to return a string instead
 * of an integer.
 *
 * Difficulty: Easy
 *
 * Link: https://oj.leetcode.com/problems/largest-number/
 *
 * Code:
 * class Solution {
 * public:
 * string largestNumber(vector<int> &num) {
 * }
 * };
 *
 * 解法:
 * 数字等长, 则大的在前. 如 9,5 则9先输出,46,48则48先.
 * 数字不等长,则按短的比较,如果不等则大的在前.如果相等,则比较长的下一个数与短的高位数,
 * 如果相等取长的,否则取大的在前.
 ****************************************************************************/
char* leetcode_179_largest_number(int* num, int size)
{
	static char _179_number[512] = {0};
	char* p = _179_number;
	int i = 0;
	int max = 0;
	int max_len = 0;
	int cur_len = 0;
	int n = size;
	int digit = 0;
	int value = 0;
	int len = 0;

	memset(_179_number, 0, sizeof(_179_number));
	if((num == NULL) || (size <= 0)) return _179_number;

	p[0] = '0';
	for(i = 0; i < size && num[i] == 0; i++);
	if(i >= size) return _179_number;

	while(n > 0)
	{
		for(i = 0; i < size && num[i] == -1; i++);
		max = i;
		for(i = max + 1;i < size; i++)
		{
			if(num[i] == -1) continue;

			for(max_len = 0, value = num[max];
				value != 0;
				value = value / 10, max_len++);
			for(cur_len = 0, value = num[i];
				value != 0;
				value = value / 10, cur_len++);
			if(max_len > cur_len)
			{
				for(value = num[max], len = max_len - cur_len;
					len > 0;
					len--, value = value / 10);
				if(value < num[i])
				{
					max = i;
				}
				else if(value == num[i])
				{
					for(value = num[max], len = max_len - cur_len;
						len > 0;
						len--, digit = value % 10, value = value / 10);
					if((num[i] < 10) && (num[i] >= digit))
					{
						max = i;
					}
					else if(num[i] / 10 > digit)
					{
						max = i;
					}
				}
			}
			else if(max_len < cur_len)
			{
				for(value = num[i], len = cur_len - max_len;
					len > 0;
					len--, value = value / 10);
				if(value > num[max])
				{
					max = i;
				}
				else if(value == num[max])
				{
					for(value = num[i], len = cur_len - max_len;
						len > 0;
						len--, digit = value % 10, value = value / 10);
					if((num[max] < 10) && (num[max] <= digit))
					{
						max = i;
					}
					else if(num[max] / 10 < digit)
					{
						max = i;
					}
				}
			}
			else
			{
				if(num[max] < num[i])
				{
					max = i;
				}
			}
		}
		p += sprintf(p, "%d", num[max]);
		num[max] = -1;
		n--;
	}

	return _179_number;
}

/*****************************************************************************
 * 以下是测试用例.
 ****************************************************************************/
static void _002_add_two_numbers(void)
{
	ListNode* l1 = NULL;
	ListNode* l2 = NULL;
	ListNode* l3 = NULL;
	ListNode* p = NULL;

	/*************************************************************************
	 * 5 + 5 = 10
	 ************************************************************************/
	l1 = ListAppend(l1, 5);
	l2 = ListAppend(l2, 5);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(l3->val, 0);
	CU_ASSERT_EQUAL(l3->next->val, 1);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 243 + 564 = 807
	 ************************************************************************/
	l1 = ListAppend(l1, 2);
	l1 = ListAppend(l1, 4);
	l1 = ListAppend(l1, 3);
	l2 = ListAppend(l2, 5);
	l2 = ListAppend(l2, 6);
	l2 = ListAppend(l2, 4);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(ListLength(l3), 3); p = l3;
	CU_ASSERT_EQUAL(p->val, 7); p = p->next;
	CU_ASSERT_EQUAL(p->val, 0); p = p->next;
	CU_ASSERT_EQUAL(p->val, 8); p = p->next;
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 2 + 3 = 5
	 ************************************************************************/
	l1 = ListAppend(l1, 2);
	l2 = ListAppend(l2, 3);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(l3->val, 5);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 2 + 8 = 10
	 ************************************************************************/
	l1 = ListAppend(l1, 2);
	l2 = ListAppend(l2, 8);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(ListLength(l3), 2);
	CU_ASSERT_EQUAL(l3->val, 0);
	CU_ASSERT_EQUAL(l3->next->val, 1);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 5 + 5
	 ************************************************************************/
	l1 = ListAppend(l1, 5);
	l2 = ListAppend(l2, 5);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(ListLength(l3), 2);
	CU_ASSERT_EQUAL(l3->val, 0);
	CU_ASSERT_EQUAL(l3->next->val, 1);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 18 + 0
	 ************************************************************************/
	l1 = ListAppend(l1, 1);
	l1 = ListAppend(l1, 8);
	l2 = ListAppend(l2, 0);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(ListLength(l3), 2);
	CU_ASSERT_EQUAL(l3->val, 1);
	CU_ASSERT_EQUAL(l3->next->val, 8);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 1 + 99
	 ************************************************************************/
	l1 = ListAppend(l1, 1);
	l2 = ListAppend(l2, 9);
	l2 = ListAppend(l2, 9);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(ListLength(l3), 3);
	CU_ASSERT_EQUAL(l3->val, 0);
	CU_ASSERT_EQUAL(l3->next->val, 0);
	CU_ASSERT_EQUAL(l3->next->next->val, 1);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 2 + 344 = 346
	 ************************************************************************/
	l1 = ListAppend(l1, 2);
	l2 = ListAppend(l2, 3);
	l2 = ListAppend(l2, 4);
	l2 = ListAppend(l2, 4);
	l3 = addTwoNumbers(l1, l2);
	CU_ASSERT_EQUAL(ListLength(l3), 3);
	CU_ASSERT_EQUAL(l3->val, 5);
	CU_ASSERT_EQUAL(l3->next->val, 4);
	CU_ASSERT_EQUAL(l3->next->next->val, 4);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 344 + 2 = 346
	 ************************************************************************/
	l1 = ListAppend(l1, 2);
	l2 = ListAppend(l2, 3);
	l2 = ListAppend(l2, 4);
	l2 = ListAppend(l2, 4);
	l3 = addTwoNumbers(l2, l1);
	CU_ASSERT_EQUAL(ListLength(l3), 3);
	CU_ASSERT_EQUAL(l3->val, 5);
	CU_ASSERT_EQUAL(l3->next->val, 4);
	CU_ASSERT_EQUAL(l3->next->next->val, 4);
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);

	/*************************************************************************
	 * 1 + 299999 = 300000
	 ************************************************************************/
	l1 = ListAppend(l1, 1);
	l2 = ListAppend(l2, 2);
	l2 = ListAppend(l2, 9);
	l2 = ListAppend(l2, 9);
	l2 = ListAppend(l2, 9);
	l2 = ListAppend(l2, 9);
	l2 = ListAppend(l2, 9);
	l3 = addTwoNumbers(l2, l1);
	CU_ASSERT_EQUAL(ListLength(l3), 6); p = l3;
	CU_ASSERT_EQUAL(p->val, 3); p = p->next;
	CU_ASSERT_EQUAL(p->val, 9); p = p->next;
	CU_ASSERT_EQUAL(p->val, 9); p = p->next;
	CU_ASSERT_EQUAL(p->val, 9); p = p->next;
	CU_ASSERT_EQUAL(p->val, 9); p = p->next;
	CU_ASSERT_EQUAL(p->val, 9); p = p->next;
	l1 = ListDestroy(l1);
	l2 = ListDestroy(l2);
	l3 = ListDestroy(l3);
}

static void _006_convert(void)
{
	CU_ASSERT_EQUAL(strcmp(convert("PAYPALISHIRING", 3), "PAHNAPLSIIGYIR"), 0);
}

static void _007_reverse(void)
{
	CU_ASSERT_EQUAL(reverse(0), 0);
	CU_ASSERT_EQUAL(reverse(123), 321);
	CU_ASSERT_EQUAL(reverse(-321), -123);
	CU_ASSERT_EQUAL(reverse(1534236469), 0);
}

static void _008_atoi(void)
{
	CU_ASSERT_EQUAL(myAtoi(NULL), 0);
	CU_ASSERT_EQUAL(myAtoi(""), 0);
	CU_ASSERT_EQUAL(myAtoi("1234"), 1234);
	CU_ASSERT_EQUAL(myAtoi("-12"), -12);
	CU_ASSERT_EQUAL(myAtoi("+2"), 2);
	CU_ASSERT_EQUAL(myAtoi(" adf sdf -12"), 0);
	CU_ASSERT_EQUAL(myAtoi(" adf -sdf 12"), 0);
	CU_ASSERT_EQUAL(myAtoi("-"), 0);
	CU_ASSERT_EQUAL(myAtoi(" adf 123sddf123"), 0);
	CU_ASSERT_EQUAL(myAtoi(" adf -1sddf123"), 0);
	CU_ASSERT_EQUAL(myAtoi("2147483648"), INT_MAX);
	CU_ASSERT_EQUAL(myAtoi("-2147483649"), INT_MIN);
	CU_ASSERT_EQUAL(myAtoi("3122147483649"), INT_MAX);
	CU_ASSERT_EQUAL(myAtoi("-3147483649"), INT_MIN);
	CU_ASSERT_EQUAL(myAtoi("+-2"), 0);
}

static void _009_is_palindrome(void)
{
	CU_ASSERT_EQUAL(isPalindrome(121), true);
	CU_ASSERT_EQUAL(isPalindrome(231), false);
	CU_ASSERT_EQUAL(isPalindrome(98789), true);
	CU_ASSERT_EQUAL(isPalindrome(-2147447412), false);
}

static void _013_roman_to_int(void)
{
	CU_ASSERT_EQUAL(romanToInt(NULL), 0);
	CU_ASSERT_EQUAL(romanToInt(""), 0);
	CU_ASSERT_EQUAL(romanToInt("I"), 1);
	CU_ASSERT_EQUAL(romanToInt("II"), 2);
	CU_ASSERT_EQUAL(romanToInt("III"), 3);
	CU_ASSERT_EQUAL(romanToInt("IV"), 4);
	CU_ASSERT_EQUAL(romanToInt("V"), 5);
	CU_ASSERT_EQUAL(romanToInt("VI"), 6);
	CU_ASSERT_EQUAL(romanToInt("VII"), 7);
	CU_ASSERT_EQUAL(romanToInt("VIII"), 8);
	CU_ASSERT_EQUAL(romanToInt("IX"), 9);
	CU_ASSERT_EQUAL(romanToInt("X"), 10);

	CU_ASSERT_EQUAL(romanToInt("XI"), 11);
	CU_ASSERT_EQUAL(romanToInt("XII"), 12);
	CU_ASSERT_EQUAL(romanToInt("XIII"), 13);
	CU_ASSERT_EQUAL(romanToInt("XIV"), 14);
	CU_ASSERT_EQUAL(romanToInt("XV"), 15);
	CU_ASSERT_EQUAL(romanToInt("XVI"), 16);
	CU_ASSERT_EQUAL(romanToInt("XVII"), 17);
	CU_ASSERT_EQUAL(romanToInt("XVIII"), 18);
	CU_ASSERT_EQUAL(romanToInt("XIX"), 19);
	CU_ASSERT_EQUAL(romanToInt("XX"), 20);
	CU_ASSERT_EQUAL(romanToInt("XXI"), 21);
	CU_ASSERT_EQUAL(romanToInt("XXII"), 22);
	CU_ASSERT_EQUAL(romanToInt("XXIX"), 29);
	CU_ASSERT_EQUAL(romanToInt("XXX"), 30);
	CU_ASSERT_EQUAL(romanToInt("XXXIV"), 34);
	CU_ASSERT_EQUAL(romanToInt("XXXV"), 35);
	CU_ASSERT_EQUAL(romanToInt("XXXIX"), 39);
	CU_ASSERT_EQUAL(romanToInt("XL"), 40);
	CU_ASSERT_EQUAL(romanToInt("L"), 50);
	CU_ASSERT_EQUAL(romanToInt("LX"), 60);
	CU_ASSERT_EQUAL(romanToInt("LXV"), 65);
	CU_ASSERT_EQUAL(romanToInt("LXXX"), 80);
	CU_ASSERT_EQUAL(romanToInt("XC"), 90);
	CU_ASSERT_EQUAL(romanToInt("XCIII"), 93);
	CU_ASSERT_EQUAL(romanToInt("XCV"), 95);
	CU_ASSERT_EQUAL(romanToInt("XCVIII"), 98);
	CU_ASSERT_EQUAL(romanToInt("XCIX"), 99);

	CU_ASSERT_EQUAL(romanToInt("C"), 100);
	CU_ASSERT_EQUAL(romanToInt("CC"), 200);
	CU_ASSERT_EQUAL(romanToInt("CCC"), 300);
	CU_ASSERT_EQUAL(romanToInt("CD"), 400);
	CU_ASSERT_EQUAL(romanToInt("D"), 500);
	CU_ASSERT_EQUAL(romanToInt("DC"), 600);
	CU_ASSERT_EQUAL(romanToInt("DCC"), 700);
	CU_ASSERT_EQUAL(romanToInt("DCCC"), 800);
	CU_ASSERT_EQUAL(romanToInt("CM"), 900);
	CU_ASSERT_EQUAL(romanToInt("CMXCIX"), 999);

	CU_ASSERT_EQUAL(romanToInt("M"), 1000);
	CU_ASSERT_EQUAL(romanToInt("MC"), 1100);
	CU_ASSERT_EQUAL(romanToInt("MCD"), 1400);
	CU_ASSERT_EQUAL(romanToInt("MD"), 1500);
	CU_ASSERT_EQUAL(romanToInt("MDC"), 1600);
	CU_ASSERT_EQUAL(romanToInt("MDCLXVI"), 1666);
	CU_ASSERT_EQUAL(romanToInt("MDCCCLXXXVIII"), 1888);
	CU_ASSERT_EQUAL(romanToInt("MDCCCXCIX"), 1899);
	CU_ASSERT_EQUAL(romanToInt("MCM"), 1900);
	CU_ASSERT_EQUAL(romanToInt("MCMLXXVI"), 1976);
	CU_ASSERT_EQUAL(romanToInt("MCMLXXXIV"), 1984);
	CU_ASSERT_EQUAL(romanToInt("MCMXC"), 1990);
	CU_ASSERT_EQUAL(romanToInt("MM"), 2000);
	CU_ASSERT_EQUAL(romanToInt("MMMCMXCIX"), 3999);
}

static void _014_longest_common_prefix(void)
{
	char* A[] = {"ab", "ab1", "ab2"};
	char* B[] = {"abc", "abdefsd", "ab"};
	char* C[] = {"abesdfsasdf", "abesxxxxysdfs", "abes1"};
	char* D[] = {"asdfes", "bdefes", "cdfeasd"};
	char* E[] = {"aa","a"};

	CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(A, ARRAY_NUM(A)), "ab"), 0);
	CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(B, ARRAY_NUM(B)), "ab"), 0);
	CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(C, ARRAY_NUM(C)), "abes"), 0);
	CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(D, ARRAY_NUM(D)), ""), 0);
	CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(E, ARRAY_NUM(E)), "a"), 0);
}

static void _019_remove_nth_node_from_end(void)
{
	ListNode* list = NULL;
	int index = 0;

	/*************************************************************************
	 * 删除倒数第二个节点
	 ************************************************************************/
	for(index = 1; index <= 5; index++)
	{
		list = ListAppend(list, index);
	}

	list = removeNthFromEnd(list, 2);
	CU_ASSERT_EQUAL(ListLength(list), 4);
	CU_ASSERT_EQUAL(list = ListDestroy(list), NULL);

	/*************************************************************************
	 * 删除倒数第一个节点,并且只有一个节点.
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = removeNthFromEnd(list, 1);
	CU_ASSERT_EQUAL(ListLength(list), 0);
	CU_ASSERT_PTR_EQUAL(list = ListDestroy(list), NULL);

	/*************************************************************************
	 * 删除多个节点中倒数第一个节点.
	 ************************************************************************/
	for(index = 1; index < 6; index++)
	{
		list = ListAppend(list, index);
	}
	CU_ASSERT_EQUAL(ListLength(list), 5);
	list = removeNthFromEnd(list, 1);
	CU_ASSERT_EQUAL(ListLength(list), 4);
	CU_ASSERT_PTR_EQUAL(list = ListDestroy(list), NULL);

	/*************************************************************************
	 * 删除只有两个节点中的倒数第二个节点,也就是头节点.
	 ************************************************************************/
	for(index = 1; index <= 2; index++)
	{
		list = ListAppend(list, index);
	}
	list = removeNthFromEnd(list, 2);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 2);
}

static void _020_is_valid(void)
{
	CU_ASSERT_EQUAL(isValid(NULL), false);
	CU_ASSERT_EQUAL(isValid(""), false);
	CU_ASSERT_EQUAL(isValid("]"), false);
	CU_ASSERT_EQUAL(isValid("}"), false);
	CU_ASSERT_EQUAL(isValid(")"), false);
	CU_ASSERT_EQUAL(isValid("[]"), true);
	CU_ASSERT_EQUAL(isValid("[)"), false);
	CU_ASSERT_EQUAL(isValid("(){}[]"), true);
	CU_ASSERT_EQUAL(isValid("((}}"), false);
	CU_ASSERT_EQUAL(isValid("(({}))[[()]]"), true);
}

static void _021_merge_two_sorted_lists(void)
{
	ListNode* l1 = NULL;
	ListNode* l2 = NULL;
	ListNode* l3 = NULL;
	ListNode* p = NULL;
	int i = 0;

	for(i = 1; i <= 9; i += 2)
	{
		l1 = ListAppend(l1, i);
	}
	for(i = 2; i <= 10; i += 2)
	{
		l2 = ListAppend(l2, i);
	}
	l3 = mergeTwoLists(l1, l2);
	p = l3;
	for(i = 1; (i <= 10) && (p != NULL); i++)
	{
		CU_ASSERT_EQUAL(p->val, i);
		p = p->next;
	}
	l3 = ListDestroy(l3);
}

static void _024_swap_pairs(void)
{
	ListNode* l = NULL;
	ListNode* p = NULL;
	int i = 0;
	int a[] = {2, 1, 4, 3};

	/*************************************************************************
	 * 标准测试,偶数个节点.
	 ************************************************************************/
	for(i = 1; i < 5; i++)
	{
		l = ListAppend(l, i);
	}
	CU_ASSERT_PTR_NOT_NULL(l = swapPairs(l));
	CU_ASSERT_EQUAL(ListLength(l), 4);
	for(p = l, i = 0; p != NULL; p = p->next, i++)
	{
		CU_ASSERT_EQUAL(a[i], p->val);
	}
	l = ListDestroy(l);

	/*************************************************************************
	 * 一个节点的情况.
	 ************************************************************************/
	l = ListAppend(l, 1);
	CU_ASSERT_PTR_NOT_NULL(l = swapPairs(l));
	CU_ASSERT_EQUAL(ListLength(l), 1);
	CU_ASSERT_EQUAL(l->val, 1);
	l = ListDestroy(l);

	/*************************************************************************
	 * 大于2的奇数个节点.
	 ************************************************************************/
	for(i = 1; i <=7; i++)
	{
		l = ListAppend(l, i);
	}
	CU_ASSERT_PTR_NOT_NULL(l = swapPairs(l));
	CU_ASSERT_EQUAL(ListLength(l), 7);
	for(p = l; p->next != NULL; p = p->next);
	CU_ASSERT_EQUAL(p->val, 7);
	l = ListDestroy(l);
}

static void _026_remove_duplicates(void)
{
	int A1[] = {1, 1, 2};
	int B1[] = {1, 2};
	int A2[] = {1};
	int B2[] = {1};
	int length = -1;
	size_t i = 0;

	length = removeDuplicates(A1, sizeof(A1) / sizeof(A1[0]));
	CU_ASSERT_EQUAL(length, 2);
	for(i = 0; i < sizeof(B1) / sizeof(B1[0]); i++)
	{
		CU_ASSERT_EQUAL(B1[i], A1[i]);
	}

	length = removeDuplicates(A2, 1);
	CU_ASSERT_EQUAL(length, 1);
	CU_ASSERT_EQUAL(A2[0], B2[0]);
}

static void _027_remove_element(void)
{
	int A1[] = {3, 3};
	int length = -1;

	length = removeElement(A1, 2, 3);
	CU_ASSERT_EQUAL(length, 0);
}

static void _028_implement_strstr(void)
{
	CU_ASSERT_EQUAL(strStr(NULL, NULL), -1);
	CU_ASSERT_EQUAL(strStr("", ""), 0);
	CU_ASSERT_EQUAL(strStr("a", ""), 0);
	CU_ASSERT_EQUAL(strStr("", "a"), -1);
	CU_ASSERT_EQUAL(strStr("abcabc", "abc"), 0);
	CU_ASSERT_EQUAL(strStr("xyxxssdfa", "abcd"), -1);
	CU_ASSERT_EQUAL(strStr("xyyyyabcddd", "abc"), 5);
	CU_ASSERT_EQUAL(strStr("xabeds", "abc"), -1);
	CU_ASSERT_EQUAL(strStr("mississippi", "issip"), 4);
	CU_ASSERT_EQUAL(strStr("mississippi", "pi"), 9);
}

static void _036_is_valid_sudoku(void)
{
	char* a1[9]=
	{
		(char*)".21......",
		(char*)"....6....",
		(char*)"......7..",
		(char*)"....5....",
		(char*)"..5......",
		(char*)"......3..",
		(char*)".........",
		(char*)"3...8.1..",
		(char*)"........8"
	};

	char* a2[9] =
	{
		(char*)".87654321",
		(char*)"2........",
		(char*)"3........",
		(char*)"4........",
		(char*)"5........",
		(char*)"6........",
		(char*)"7........",
		(char*)"8........",
		(char*)"9........"
	};

	char* a3[9] = 
	{
		"......5..",
		".........",
		"........3",
		".2.7.....",
		"8365....1",
		".....1...",
		"2.......5",
		"........7",
		"...4...7."
	};

	CU_ASSERT_EQUAL(isValidSudoku(NULL, 0, 0), false);
	CU_ASSERT_EQUAL(isValidSudoku(a1, 9, 9), true);
	CU_ASSERT_EQUAL(isValidSudoku(a2, 9, 9), true);
	CU_ASSERT_EQUAL(isValidSudoku(a3, 9, 9), false);
}

static void _038_count_and_say(void)
{
	CU_ASSERT_EQUAL(strcmp(countAndSay(1), "1"), 0);
	CU_ASSERT_EQUAL(strcmp(countAndSay(2), "11"), 0);
	CU_ASSERT_EQUAL(strcmp(countAndSay(3), "21"), 0);
	CU_ASSERT_EQUAL(strcmp(countAndSay(4), "1211"), 0);
	CU_ASSERT_EQUAL(strcmp(countAndSay(5), "111221"), 0);
	CU_ASSERT_EQUAL(strcmp(countAndSay(20), "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211"), 0);
}

static void _058_length_of_last_word(void)
{
	CU_ASSERT_EQUAL(lengthOfLastWord(NULL), 0);
	CU_ASSERT_EQUAL(lengthOfLastWord("avsdfe"), 6);
	CU_ASSERT_EQUAL(lengthOfLastWord("avsdfe "), 6);
	CU_ASSERT_EQUAL(lengthOfLastWord("avsdfe  1 "), 1);
	CU_ASSERT_EQUAL(lengthOfLastWord(" aaa "), 3);
	CU_ASSERT_EQUAL(lengthOfLastWord("a"), 1);
}

static void _061_rotate_right(void)
{
	ListNode* list = NULL;

	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = ListAppend(list, 5);
	list = rotateRight(list, 2);
	CU_ASSERT_EQUAL(ListLength(list), 5);
	CU_ASSERT_EQUAL(list->val, 4);
	CU_ASSERT_EQUAL(list->next->val, 5);
	list = ListDestroy(list);

	list = ListAppend(list, 1);
	list = rotateRight(list, 1);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = rotateRight(list, 3);
	CU_ASSERT_EQUAL(ListLength(list), 2);
	CU_ASSERT_EQUAL(list->val, 2);
	CU_ASSERT_EQUAL(list->next->val, 1);
	list = ListDestroy(list);

	list = ListAppend(list, 1);
	list = rotateRight(list, 99);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = ListAppend(list, 5);
	list = rotateRight(list, 5);
	CU_ASSERT_EQUAL(ListLength(list), 5);
	CU_ASSERT_EQUAL(list->val, 1);
	CU_ASSERT_EQUAL(list->next->val, 2);
	list = ListDestroy(list);
}

static void _066_plus_one(void)
{
	int a1[] = {6, 2, 7, 9};
	int a2[] = {9, 9, 0};
	int size = 0;
	int* b = 0;

	/*************************************************************************
	 * 6279 + 1 = 6280
	 ************************************************************************/
	CU_ASSERT_PTR_NOT_NULL(b = plusOne(a1, 4, &size));
	CU_ASSERT_EQUAL(size, 4);
	CU_ASSERT_EQUAL(b[0], 6);
	CU_ASSERT_EQUAL(b[1], 2);
	CU_ASSERT_EQUAL(b[2], 8);
	CU_ASSERT_EQUAL(b[3], 0);

	/*************************************************************************
	 * 99 + 1 = 100
	 ************************************************************************/
	CU_ASSERT_PTR_NOT_NULL(b = plusOne(a2, 2, &size));
	CU_ASSERT_EQUAL(size, 3);
	CU_ASSERT_EQUAL(b[0], 1);
	CU_ASSERT_EQUAL(b[1], 0);
	CU_ASSERT_EQUAL(b[2], 0);
}

static void _067_add_binary(void)
{
	CU_ASSERT_EQUAL(addBinary(NULL, NULL), NULL);
	CU_ASSERT_EQUAL(strcmp(addBinary("11", NULL), "11"), 0);
	CU_ASSERT_EQUAL(strcmp(addBinary(NULL, "11"), "11"), 0);
	CU_ASSERT_EQUAL(strcmp(addBinary("11", "1"), "100"), 0);
	CU_ASSERT_EQUAL(strcmp(addBinary("1", "111"), "1000"), 0);
	CU_ASSERT_EQUAL(strcmp(addBinary("1010", "1011"), "10101"), 0);
}

static void _070_climb_stairs(void)
{
	CU_ASSERT_EQUAL(climbStairs(1), 1);
	CU_ASSERT_EQUAL(climbStairs(2), 2);
	CU_ASSERT_EQUAL(climbStairs(3), 3);
}

static void _078_subsets(void)
{
	int A[] = {1, 2, 3};
	int B[] = {4, 1, 0};
	int** result = NULL;
	int* column = NULL;
	int size = 0;
	char resstr[256] = {0};
	char* buf = NULL;
	int i = 0;
	int j = 0;

	CU_ASSERT_PTR_NOT_NULL(result = subsets(A, ARRAY_NUM(A), &column, &size));
	CU_ASSERT_EQUAL(size, 1 << ARRAY_NUM(A));
	free(column);
	free(result);

	CU_ASSERT_PTR_NOT_NULL(result = subsets(B, ARRAY_NUM(B), &column, &size));
	CU_ASSERT_EQUAL(size, 1 << ARRAY_NUM(B));

	buf = resstr;
	buf += sprintf(buf, "[");
	for(i = 0; i < size; i++)
	{
		buf += sprintf(buf, "[");
		for(j = 0; j < column[i]; j++)
		{
			buf += sprintf(buf, "%d", result[i][j]);
			if((j < column[i]) && (j != column[i] - 1))
			{
				buf += sprintf(buf, ",");
			}
		}
		buf += sprintf(buf, "]");
		if(i != (size - 1))
		{
			buf += sprintf(buf, ",");
		}
	}
	buf += sprintf(buf, "]");

	CU_ASSERT_EQUAL(
		strcmp(resstr, "[[],[4],[1],[1,4],[0],[0,4],[0,1],[0,1,4]]"), 0);
	free(column);
	free(result);
}

static void _082_delete_duplicates_ii(void)
{
	ListNode* list = NULL;
	ListNode* p = NULL;
	int i = 0;

	/*************************************************************************
	 * Input:1->2->2->2->3->4->4->4->5->6->6 Output:1->3->5
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 2);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = ListAppend(list, 4);
	list = ListAppend(list, 4);
	list = ListAppend(list, 5);
	list = ListAppend(list, 6);
	list = ListAppend(list, 6);
	list = deleteDuplicatesII(list);
	CU_ASSERT_EQUAL(ListLength(list), 3);
	for(i = 1, p = list; (i <= 5) && (p != NULL); i += 2, p = p->next)
	{
		CU_ASSERT_EQUAL(p->val, i);
	}
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1->1->1->1 Output:Empty
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = deleteDuplicatesII(list);
	CU_ASSERT_EQUAL(ListLength(list), 0);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1->1->1->2->3->6->6 Output:2->3
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 6);
	list = ListAppend(list, 6);
	list = deleteDuplicatesII(list);
	CU_ASSERT_EQUAL(ListLength(list), 2);
	CU_ASSERT_EQUAL(list->val, 2);
	CU_ASSERT_EQUAL(list->next->val, 3);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1 Output:1
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = deleteDuplicatesII(list);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1->2->3->4 Output:1->2->3->4
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = deleteDuplicatesII(list);
	CU_ASSERT_EQUAL(ListLength(list), 4);
	list = ListDestroy(list);
}

static void _083_delete_duplicates(void)
{
	ListNode* list = NULL;
	ListNode* p = NULL;
	int i = 0;

	/*************************************************************************
	 * Input:1->2->2->2->3->4->4->4->5->6->6 Output:1->2->3->4->5->6
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 2);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = ListAppend(list, 4);
	list = ListAppend(list, 4);
	list = ListAppend(list, 5);
	list = ListAppend(list, 6);
	list = ListAppend(list, 6);
	list = deleteDuplicates(list);
	CU_ASSERT_EQUAL(ListLength(list), 6);
	for(i = 1, p = list; (i <= 6) && (p != NULL); i += 1, p = p->next)
	{
		CU_ASSERT_EQUAL(p->val, i);
	}
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1->1->1->1 Output:1
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = deleteDuplicates(list);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1->1->1->2->3->6->6 Output:1->2->3->6
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 6);
	list = ListAppend(list, 6);
	list = deleteDuplicates(list);
	CU_ASSERT_EQUAL(ListLength(list), 4);
	CU_ASSERT_EQUAL(list->val, 1);
	CU_ASSERT_EQUAL(list->next->val, 2);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1 Output:1
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = deleteDuplicates(list);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:1->2->3->4 Output:1->2->3->4
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = deleteDuplicates(list);
	CU_ASSERT_EQUAL(ListLength(list), 4);
	list = ListDestroy(list);
}

static void _086_partition_list(void)
{
	ListNode* list = NULL;
	ListNode* p = NULL;
	size_t i = 0;
	int a1[] = {1, 4, 3, 2, 5, 2};
	int b1[] = {1, 2, 2, 4, 3, 5};
	int a2[] = {4, 1, 3, 2, 5, 2};
	int b2[] = {1, 2, 2, 4, 3, 5};

	/*************************************************************************
	 * Input:1->4->3->2->5->2 Output:1->2->2->4->3->5
	 ************************************************************************/
	for(i = 0; i < ARRAY_NUM(a1); i++)
	{
		list = ListAppend(list, a1[i]);
	}
	list = partition(list, 3);
	CU_ASSERT_EQUAL(ListLength(list), ARRAY_NUM(a1));
	for(i = 0, p = list; i < ARRAY_NUM(b1); i++, p = p->next)
	{
		CU_ASSERT_EQUAL(p->val, b1[i]);
	}
	list = ListDestroy(list);

	/*************************************************************************
	 * Input: 4->1->3->2->5->2 3 Output:1->2->4->3->5
	 ************************************************************************/
	for(i = 0; i < ARRAY_NUM(a2); i++)
	{
		list = ListAppend(list, a2[i]);
	}
	list = partition(list, 3);
	CU_ASSERT_EQUAL(ListLength(list), ARRAY_NUM(a2));
	for(i = 0, p = list; i < ARRAY_NUM(b2); i++, p = p->next)
	{
		CU_ASSERT_EQUAL(p->val, b2[i]);
	}
	list = ListDestroy(list);

	/*************************************************************************
	 * Input: 4->1->3->2->5->2 1 Output:4->1->3->2->5->2
	 ************************************************************************/
	for(i = 0; i < ARRAY_NUM(a2); i++)
	{
		list = ListAppend(list, a2[i]);
	}
	list = partition(list, 1);
	CU_ASSERT_EQUAL(ListLength(list), ARRAY_NUM(a2));
	for(i = 0, p = list; i < ARRAY_NUM(b2); i++, p = p->next)
	{
		CU_ASSERT_EQUAL(p->val, a2[i]);
	}
	list = ListDestroy(list);

	/*************************************************************************
	 * Input: {1}, 2 Output: {1}
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = partition(list, 2);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input: {3,1,2},3 Output:{1,2,3}
	 ************************************************************************/
	list = ListAppend(list, 3);
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = partition(list, 3);
	CU_ASSERT_EQUAL(ListLength(list), 3);
	list = ListDestroy(list);
}

static void _088_merge_sorted_array(void)
{
	int A1[] = {1,2,4,5,6,-1};
	int B1[] = {3};
	int C1[] = {1,2,3,4,5,6};
	int A2[] = {-1,-1,0,0,0,0};
	int B2[] = {-1,0};
	int C2[] = {-1,-1,-1,0,0,0};
	size_t i = 0;

	merge(A1, 5, B1, 1);
	for(i = 0; i < sizeof(A1) / sizeof(A1[0]); i++)
	{
		CU_ASSERT_EQUAL(C1[i], A1[i]);
	}

	merge(A2, 4, B2, 2);
	for(i = 0; i < sizeof(A2) / sizeof(A2[0]); i++)
	{
		CU_ASSERT_EQUAL(C2[i], A2[i]);
	}
}

static void _092_reverse_between(void)
{
	ListNode* l = NULL;
	ListNode* p = NULL;
	size_t i = 0;
	int a[] = {1, 4, 3, 2, 5};

	/*************************************************************************
	 * 标准测试.
	 ************************************************************************/
	for(i = 1; i <= 5; i++)
	{
		l = ListAppend(l, i);
	}
	CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 2, 4));
	CU_ASSERT_EQUAL(ListLength(l), 5);
	for(p = l, i = 0; (p != NULL) && (i < sizeof(a) / sizeof(a[0]));
		p = p->next, i++)
	{
		CU_ASSERT_EQUAL(p->val, a[i]);
	}
	l = ListDestroy(l);

	/*************************************************************************
	 * m = n = 等于链表长度
	 ************************************************************************/
	for(i = 1; i <= 5; i++)
	{
		l = ListAppend(l, i);
	}
	CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 5, 5));
	CU_ASSERT_EQUAL(ListLength(l), 5);
	l = ListDestroy(l);

	/*************************************************************************
	 * 只有一个节点的情况.
	 ************************************************************************/
	l = ListAppend(l, 5);
	CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 1, 1));
	CU_ASSERT_EQUAL(ListLength(l), 1);
	l = ListDestroy(l);

	/*************************************************************************
	 * 只有两个节点的情况.
	 ************************************************************************/
	l = ListAppend(l, 3);
	l = ListAppend(l, 5);
	CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 1, 1));
	CU_ASSERT_EQUAL(ListLength(l), 2);
	CU_ASSERT_EQUAL(l->val, 3);
	CU_ASSERT_EQUAL(l->next->val, 5);
	CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 1, 2));
	CU_ASSERT_EQUAL(ListLength(l), 2);
	CU_ASSERT_EQUAL(l->val, 5);
	CU_ASSERT_EQUAL(l->next->val, 3);
	l = ListDestroy(l);
}

static void _094_inorder_traversal(void)
{
	TreeNode* t = NULL;
	int* l = NULL;
	int size = 0;

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,#,2,3}"));
	CU_ASSERT_PTR_NOT_NULL(l = inorderTraversal(t, &size));
	CU_ASSERT_EQUAL(3, size);
	CU_ASSERT_EQUAL(1, l[0]);
	CU_ASSERT_EQUAL(3, l[1]);
	CU_ASSERT_EQUAL(2, l[2]);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
	free(l);
}

static void _098_is_valid_bst(void)
{
	TreeNode* t = NULL;

	CU_ASSERT_EQUAL(isValidBST(NULL), true);

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1}"));
	CU_ASSERT_EQUAL(isValidBST(t), true);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2}"));
	CU_ASSERT_EQUAL(isValidBST(t), false);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,1}"));
	CU_ASSERT_EQUAL(isValidBST(t), false);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{3,#,2}"));
	CU_ASSERT_EQUAL(isValidBST(t), false);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{4,2,6,1,3,5,7}"));
	CU_ASSERT_EQUAL(isValidBST(t), true);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{10,5,15,#,#,6,20}"));
	CU_ASSERT_EQUAL(isValidBST(t), false);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{-2147483648}"));
	CU_ASSERT_EQUAL(isValidBST(t), true);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{-2147483648,#,2147483647}"));
	CU_ASSERT_EQUAL(isValidBST(t), true);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}

static void _100_same_tree(void)
{
	TreeNode* t1 = NULL;
	TreeNode* t2 = NULL;

	t1 = TreeNew(1, NULL, NULL, NULL);
	CU_ASSERT_EQUAL(isSameTree(NULL, NULL), true);
	CU_ASSERT_EQUAL(isSameTree(t1, NULL), false);
	CU_ASSERT_EQUAL(isSameTree(NULL, t1), false);
	CU_ASSERT_PTR_NULL(t1 = TreeDestroy(t1));

	t1 = TreeNewByString("2,3,4,#,5,6,#,#,#,#,#,");
	t2 = TreeNewByString("2,3,4,#,5,6,#,#,#,#,#,");
	CU_ASSERT_EQUAL(isSameTree(t1, t2), true);
	CU_ASSERT_PTR_NULL(t1 = TreeDestroy(t1));
	CU_ASSERT_PTR_NULL(t2 = TreeDestroy(t2));

	t1 = TreeNewByString("2,3,4,#,#,#,#,");
	t2 = TreeNewByString("2,3,#,#,#,");
	CU_ASSERT_EQUAL(isSameTree(t1, t2), false);
	CU_ASSERT_PTR_NULL(t1 = TreeDestroy(t1));
	CU_ASSERT_PTR_NULL(t2 = TreeDestroy(t2));
}

static void _101_is_symmetric(void)
{
	TreeNode* t = NULL;

	CU_ASSERT_EQUAL(isSymmetric(NULL), true);

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1}"));
	CU_ASSERT_EQUAL(isSymmetric(t), true);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,2,3,4,4,3}"));
	CU_ASSERT_EQUAL(isSymmetric(t), true);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,2,#,3,#,3}"));
	CU_ASSERT_EQUAL(isSymmetric(t), false);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2}"));
	CU_ASSERT_EQUAL(isSymmetric(t), false);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}

static void _102_level_order(void)
{
	TreeNode* t = NULL;
	int** vector = NULL;
	int* columnSizes = NULL;
	int height = NULL;

	/*************************************************************************
	 * Input:{3,9,20,#,#,15,7}, Output:[[3],[9,20],[15,7]]
	 ************************************************************************/
	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{3,9,20,#,#,15,7}"));
	CU_ASSERT_PTR_NOT_NULL(vector = levelOrder(t, &columnSizes, &height));
	CU_ASSERT_PTR_NOT_NULL(columnSizes);
	CU_ASSERT_EQUAL(height, 3);
	CU_ASSERT_EQUAL(columnSizes[0], 1);
	CU_ASSERT_EQUAL(vector[0][0], 3);
	CU_ASSERT_EQUAL(columnSizes[1], 2);
	CU_ASSERT_EQUAL(vector[1][0], 9);
	CU_ASSERT_EQUAL(vector[1][1], 20);
	CU_ASSERT_EQUAL(columnSizes[2], 2);
	CU_ASSERT_EQUAL(vector[2][0], 15);
	CU_ASSERT_EQUAL(vector[2][1], 7);

	free(vector);
	free(columnSizes);
	t = TreeDestroy(t);
	vector = NULL;
	columnSizes = NULL;
	height = 0;

	/*************************************************************************
	 * Input:{1,2,3,4,5}, Output:[[1],[2,3],[4,5]]
	 ************************************************************************/
	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,3,4,5}"));
	CU_ASSERT_PTR_NOT_NULL(vector = levelOrder(t, &columnSizes, &height));
	CU_ASSERT_PTR_NOT_NULL(columnSizes);
	CU_ASSERT_EQUAL(height, 3);
	CU_ASSERT_EQUAL(columnSizes[0], 1);
	CU_ASSERT_EQUAL(vector[0][0], 1);
	CU_ASSERT_EQUAL(columnSizes[1], 2);
	CU_ASSERT_EQUAL(vector[1][0], 2);
	CU_ASSERT_EQUAL(vector[1][1], 3);
	CU_ASSERT_EQUAL(columnSizes[2], 2);
	CU_ASSERT_EQUAL(vector[2][0], 4);
	CU_ASSERT_EQUAL(vector[2][1], 5);

	free(vector);
	free(columnSizes);
	t = TreeDestroy(t);
}

static void _104_max_depth(void)
{
	TreeNode* t = NULL;

	CU_ASSERT_EQUAL(maxDepth(NULL), 0);

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,#,#,"));
	CU_ASSERT_EQUAL(maxDepth(t), 1);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,3,4,#,5,6,#,#,#,"));
	CU_ASSERT_EQUAL(maxDepth(t), 5);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}

static void _107_level_order_bottom(void)
{
	TreeNode* t = NULL;
	int** vector = NULL;
	int* columnSizes = NULL;
	int height = 0;

	/*************************************************************************
	 * Input:{3,9,20,#,#,15,7}, Output:[[15,7],[9,20],[3]]
	 ************************************************************************/
	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{3,9,20,#,#,15,7}"));
	CU_ASSERT_PTR_NOT_NULL(vector = levelOrderBottom(t, &columnSizes, &height));
	CU_ASSERT_PTR_NOT_NULL(columnSizes);
	CU_ASSERT_EQUAL(height, 3);

	CU_ASSERT_EQUAL(columnSizes[0], 2);
	CU_ASSERT_EQUAL(vector[0][0], 15);
	CU_ASSERT_EQUAL(vector[0][1], 7);
	CU_ASSERT_EQUAL(columnSizes[1], 2);
	CU_ASSERT_EQUAL(vector[1][0], 9);
	CU_ASSERT_EQUAL(vector[1][1], 20);
	CU_ASSERT_EQUAL(columnSizes[2], 1);
	CU_ASSERT_EQUAL(vector[2][0], 3);

	free(vector);
	free(columnSizes);
	t = TreeDestroy(t);
}

static void _110_lbe_is_balanced(void)
{
	CU_ASSERT_EQUAL(leetcode_110_is_balanced(NULL), true);
}

static void _111_min_depth(void)
{
	TreeNode* t = NULL;

	CU_ASSERT_EQUAL(leetcode_111_min_depth(NULL), 0);

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,#,#,"));
	CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 1);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,3,4,#,5,6,#,#,#,"));
	CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 5);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("1,2,#,#,#,"));
	CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 2);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("1,2,3,5,#,#,#,4,#,#,#,"));
	CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 3);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,3,4,#,5,6,#,#,#,#,1,#,#,#,"));
	CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 3);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}

static void _112_path_sum(void)
{
	TreeNode* root = NULL;

	root = TreeNew(5, NULL, NULL, NULL);
	root->left = TreeNew(4, NULL, NULL, NULL);
	root->right = TreeNew(8, NULL, NULL, NULL);
	root->left->left = TreeNew(11, NULL, NULL, NULL);
	root->left->left->left = TreeNew(7, NULL, NULL, NULL);
	root->left->left->right = TreeNew(2, NULL, NULL, NULL);
	root->right->left = TreeNew(13, NULL, NULL, NULL);
	root->right->right = TreeNew(4, NULL, NULL, NULL);
	root->right->right->right = TreeNew(1, NULL, NULL, NULL);

	CU_ASSERT_EQUAL(leetcode_112_has_path_sum(root, 22), 1);
	CU_ASSERT_PTR_NULL(root = TreeDestroy(root));
}

static void _114_flatten(void)
{
	TreeNode* t = NULL;

	t = TreeNewByStringOJ("{1}");
	CU_ASSERT_PTR_NOT_NULL(t);
	leetcode_114_flatten(t);
	CU_ASSERT_PTR_NOT_NULL(t);
	CU_ASSERT_EQUAL(1, t->val);
	TreeDestroy(t);

	t = TreeNewByStringOJ("{1,2,5,3,4,#,6}");
	CU_ASSERT_PTR_NOT_NULL(t);
	leetcode_114_flatten(t);
	CU_ASSERT_PTR_NOT_NULL(t);
	CU_ASSERT_EQUAL(1, t->val);
	CU_ASSERT_EQUAL(2, t->right->val);
	CU_ASSERT_EQUAL(3, t->right->right->val);
	CU_ASSERT_EQUAL(4, t->right->right->right->val);
	CU_ASSERT_EQUAL(5, t->right->right->right->right->val);
	CU_ASSERT_EQUAL(6, t->right->right->right->right->right->val);
	TreeDestroy(t);
}

static void _116_connect(void)
{
	TreeLinkNode* t;

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,3,4,5,6,7"));
	leetcode_116_connect(t);
	CU_ASSERT_EQUAL(t->val, 1);
	CU_ASSERT_EQUAL(t->next, NULL);
	CU_ASSERT_EQUAL(t->left->val, 2);
	CU_ASSERT_EQUAL(t->left->next->val, 3);
	CU_ASSERT_EQUAL(t->right, t->left->next);
	CU_ASSERT_EQUAL(t->left->left->val, 4);
	CU_ASSERT_EQUAL(t->left->left->next->val, 5);
	CU_ASSERT_EQUAL(t->left->left->next, t->left->right);
	CU_ASSERT_EQUAL(t->right->left->val, 6);
	CU_ASSERT_EQUAL(t->right->right, t->right->left->next);
	CU_ASSERT_EQUAL(t->right->left->next->val, 7);
	CU_ASSERT_EQUAL(t->left->left->next->next->val, 6);
	CU_ASSERT_EQUAL(t->left->left->next->next->next->val, 7);
	CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}

static void _118_generate(void)
{
#if 0
	list_t* row = NULL;
	list_t* rows = NULL;
	int val = 0;

	CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(0));
	CU_ASSERT_EQUAL(lbe_list_size(rows), 0);
	lbe_list_free(rows);

	CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(1));
	CU_ASSERT_EQUAL(lbe_list_size(rows), 1);
	CU_ASSERT_EQUAL(lbe_list_get(rows, 0, (void**)&row), LBE_OK);
	CU_ASSERT_EQUAL(lbe_list_size(row), 1);
	CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	lbe_list_free(rows);

	CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(3));
	CU_ASSERT_EQUAL(lbe_list_size(rows), 3);
	CU_ASSERT_EQUAL(lbe_list_get(rows, 0, (void**)&row), LBE_OK);
	CU_ASSERT_EQUAL(lbe_list_size(row), 1);
	CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	CU_ASSERT_EQUAL(lbe_list_get(rows, 1, (void**)&row), LBE_OK);
	CU_ASSERT_EQUAL(lbe_list_size(row), 2);
	CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	CU_ASSERT_EQUAL(lbe_list_get(row, 1, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	CU_ASSERT_EQUAL(lbe_list_get(rows, 2, (void**)&row), LBE_OK);
	CU_ASSERT_EQUAL(lbe_list_size(row), 3);
	CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	CU_ASSERT_EQUAL(lbe_list_get(row, 1, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 2);
	CU_ASSERT_EQUAL(lbe_list_get(row, 2, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	lbe_list_free(rows);

	CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(4));
	CU_ASSERT_EQUAL(lbe_list_size(rows), 4);
	CU_ASSERT_EQUAL(lbe_list_get(rows, 3, (void**)&row), LBE_OK);
	CU_ASSERT_EQUAL(lbe_list_size(row), 4);
	CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	CU_ASSERT_EQUAL(lbe_list_get(row, 1, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 3);
	CU_ASSERT_EQUAL(lbe_list_get(row, 2, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 3);
	CU_ASSERT_EQUAL(lbe_list_get(row, 3, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	lbe_list_free(rows);
#endif
}

static void _119_get_row(void)
{
#if 0
	list_t* l = NULL;
	int _3[] = {1, 3, 3, 1};
	int _4[] = {1, 4, 6, 4, 1};
	int _5[] = {1, 5, 10, 10, 5, 1};
	unsigned int i = 0;
	int val = 0;

	CU_ASSERT_PTR_NOT_NULL(l = leetcode_119_get_row(ARRAY_NUM(_3) - 1));
	CU_ASSERT_EQUAL(lbe_list_size(l), ARRAY_NUM(_3));
	for(i = 0; i < ARRAY_NUM(_3); i++)
	{
		CU_ASSERT_EQUAL(lbe_list_get(l, i, (void**)&val), LBE_OK);
		CU_ASSERT_EQUAL(val, _3[i]);
	}
	lbe_list_free(l);

	CU_ASSERT_PTR_NOT_NULL(l = leetcode_119_get_row(ARRAY_NUM(_4) - 1));
	CU_ASSERT_EQUAL(lbe_list_size(l), ARRAY_NUM(_4));
	for(i = 0; i < ARRAY_NUM(_4); i++)
	{
		CU_ASSERT_EQUAL(lbe_list_get(l, i, (void**)&val), LBE_OK);
		CU_ASSERT_EQUAL(val, _4[i]);
	}
	lbe_list_free(l);

	CU_ASSERT_PTR_NOT_NULL(l = leetcode_119_get_row(ARRAY_NUM(_5) - 1));
	CU_ASSERT_EQUAL(lbe_list_size(l), ARRAY_NUM(_5));
	for(i = 0; i < ARRAY_NUM(_5); i++)
	{
		CU_ASSERT_EQUAL(lbe_list_get(l, i, (void**)&val), LBE_OK);
		CU_ASSERT_EQUAL(val, _5[i]);
	}
	lbe_list_free(l);
#endif
}

static void _125_is_palindrome(void)
{
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome(NULL), false);
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome(""), true);
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome("A man, a plan, a canal: Panama"), true);
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome("race a car"), false);
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome("Nella's simple hymn: \"I attain my help, Miss Allen.\""), true);
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome("1a2"), false);
	CU_ASSERT_EQUAL(leetcode_125_is_palindrome("Sore was I ere I saw Eros."), true);
}

static void _136_single_number(void)
{
	int A[] = {1, 2, 3, 4, 3, 1,4};
	CU_ASSERT_EQUAL(leetcode_136_single_number(A, ARRAY_NUM(A)), 2);
}

static void _137_single_number_ii(void)
{
	int A[] = {1, 3, 5, 3, 2, 1, 1, 5, 3, 5};
	CU_ASSERT_EQUAL(leetcode_137_signle_number_ii(A, ARRAY_NUM(A)), 2);
}

static void _141_has_cycle(void)
{
	ListNode* list = NULL;
	ListNode* tail = NULL;
	int i = 0;

	for(i = 1; i <= 10; i++) list = ListAppend(list, i);
	CU_ASSERT_PTR_NOT_NULL(tail = ListMakeCycle(list, 3));
	CU_ASSERT_EQUAL(leetcode_141_has_cycle(list), true);
	tail->next = NULL;
	list = ListDestroy(list);
}

static void _142_detect_cycle(void)
{
	ListNode* list = NULL;
	ListNode* tail = NULL;
	ListNode* cycle = NULL;
	int i = 0;

	for(i = 1; i<= 10; i++) list = ListAppend(list, i);
	CU_ASSERT_PTR_NOT_NULL(tail = ListMakeCycle(list, 2));
	CU_ASSERT_EQUAL(leetcode_141_has_cycle(list), true);
	CU_ASSERT_PTR_NOT_NULL(cycle = leetcode_142_detect_cycle(list));
	CU_ASSERT_PTR_EQUAL(cycle, list->next->next);
	tail->next = NULL;
	list = ListDestroy(list);

	list = ListAppend(list, 1);
	CU_ASSERT_PTR_NULL(cycle = leetcode_142_detect_cycle(list));
	list = ListDestroy(list);

	list = ListAppend(list, 1);
	list->next = list;
	CU_ASSERT_EQUAL(leetcode_141_has_cycle(list), true);
	CU_ASSERT_PTR_EQUAL(list, cycle = leetcode_142_detect_cycle(list));
	list->next = NULL;
	list = ListDestroy(list);
}

static void _144_preorder_traversal(void)
{
#if 0
	TreeNode* t = NULL;
	list_t* list = NULL;
	int val = 0;

	CU_ASSERT_PTR_NULL(leetcode_144_preorder_traversal(NULL));

	CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,#,2,3}"));
	CU_ASSERT_PTR_NOT_NULL(list = leetcode_144_preorder_traversal(t));
	CU_ASSERT_EQUAL(lbe_list_size(list), 3);
	CU_ASSERT_EQUAL(lbe_list_get(list, 0, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 1);
	CU_ASSERT_EQUAL(lbe_list_get(list, 1, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 2);
	CU_ASSERT_EQUAL(lbe_list_get(list, 2, (void**)&val), LBE_OK);
	CU_ASSERT_EQUAL(val, 3);
	lbe_list_free(list);
	t = TreeDestroy(t);
#endif
}

static void _143_reorder_list(void)
{
	ListNode* list = NULL;

	/*************************************************************************
	 * Input: {1,2,3,4} Output:{1,4,2,3}
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	leetcode_143_reorder_list(list);
	CU_ASSERT_EQUAL(ListLength(list), 4);
	CU_ASSERT_EQUAL(list->val, 1);
	CU_ASSERT_EQUAL(list->next->val, 4);
	CU_ASSERT_EQUAL(list->next->next->val, 2);
	CU_ASSERT_EQUAL(list->next->next->next->val, 3);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:{1}, Output:{1}
	 ************************************************************************/
	list = ListAppend(list, 1);
	leetcode_143_reorder_list(list);
	CU_ASSERT_EQUAL(ListLength(list), 1);
	CU_ASSERT_EQUAL(list->val, 1);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:{1,2}, Output:{1,2}
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	leetcode_143_reorder_list(list);
	CU_ASSERT_EQUAL(ListLength(list), 2);
	CU_ASSERT_EQUAL(list->val, 1);
	CU_ASSERT_EQUAL(list->next->val, 2);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:{1,2,3}, Output:{1,3,2}
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	leetcode_143_reorder_list(list);
	CU_ASSERT_EQUAL(ListLength(list), 3);
	CU_ASSERT_EQUAL(list->val, 1);
	CU_ASSERT_EQUAL(list->next->val, 3);
	CU_ASSERT_EQUAL(list->next->next->val, 2);
	list = ListDestroy(list);

	/*************************************************************************
	 * Input:{1,2,3,4,5}, Output:{1,5,2,4,3}
	 ************************************************************************/
	list = ListAppend(list, 1);
	list = ListAppend(list, 2);
	list = ListAppend(list, 3);
	list = ListAppend(list, 4);
	list = ListAppend(list, 5);
	leetcode_143_reorder_list(list);
	CU_ASSERT_EQUAL(ListLength(list), 5);
	CU_ASSERT_EQUAL(list->val, 1);
	CU_ASSERT_EQUAL(list->next->val, 5);
	CU_ASSERT_EQUAL(list->next->next->val, 2);
	CU_ASSERT_EQUAL(list->next->next->next->val, 4);
	CU_ASSERT_EQUAL(list->next->next->next->next->val, 3);
	list = ListDestroy(list);
}

static void _147_insertion_sort_list(void)
{
	ListNode* list = NULL;
	ListNode* p = NULL;
	int i = 0;

	list = ListAppend(list, 3);
	list = ListAppend(list, 5);
	list = ListAppend(list, 2);
	list = ListAppend(list, 4);
	list = ListAppend(list, 1);
	list = leetcode_147_insertion_sort_list(list);
	CU_ASSERT_EQUAL(ListLength(list), 5);
	p = list;
	for(i = 1; i <= 5; i++)
	{
		CU_ASSERT_EQUAL(p->val, i);
		p = p->next;
	}
	list = ListDestroy(list);
}

static void _155_min_stack(void)
{
#if 0
	MinStack* ms = NULL;

	CU_ASSERT_PTR_NOT_NULL(ms = leetcode_155_min_stack());
	ms->push(ms, 10);
	CU_ASSERT_EQUAL(ms->top(ms), 10);
	ms->push(ms, 20);
	CU_ASSERT_EQUAL(ms->top(ms), 20);
	CU_ASSERT_EQUAL(ms->getMin(ms), 10);
	ms->push(ms, 9);
	CU_ASSERT_EQUAL(ms->getMin(ms), 9);
	ms->push(ms, 21);
	ms->push(ms, 8);
	CU_ASSERT_EQUAL(ms->getMin(ms), 8);
	ms->pop(ms);
	CU_ASSERT_EQUAL(ms->getMin(ms), 9);
	CU_ASSERT_EQUAL(ms->top(ms), 21);
	ms->pop(ms);
	CU_ASSERT_EQUAL(ms->getMin(ms), ms->top(ms));

	MinStackFree(ms);
#endif
}

static void _160_intersection_linked_list(void)
{
	ListNode* a = NULL;
	ListNode* b = NULL;
	ListNode* c = NULL;
	ListNode* p = NULL;
	ListNode* node = NULL;
	int i = 0;
	int la = 0;
	int lb = 0;
	int lc = 0;

	for(i = 0; i < 5; i++)
	{
		a = ListAppend(a, i);
	}
	for(i = 5; i < 10; i++)
	{
		b = ListAppend(b, i);
	}
	for(i = 10; i < 15; i++)
	{
		c = ListAppend(c, i);
	}

	la = ListLength(a);
	lb = ListLength(b);
	lc = ListLength(c);

	for(p = a; p->next != NULL; p = p->next);
	p->next = c;
	for(p = b; p->next != NULL; p = p->next);
	p->next = c;
	CU_ASSERT_EQUAL(ListLength(a), la + lc);
	CU_ASSERT_EQUAL(ListLength(b), lb + lc);
	node = leetcode_160_get_intersection_node(a, b);
	CU_ASSERT_PTR_EQUAL(node, c);
}

static void _165_compare_version(void)
{
	CU_ASSERT_EQUAL(leetcode_165_compare_version(NULL, NULL), 0);
	CU_ASSERT_EQUAL(leetcode_165_compare_version(NULL, "0.1"), 0);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1", NULL), 0);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1", "1.1"), -1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("1.1", "1.2"), -1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("1.2", "13.37"), -1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1.2", "0.1.3"), -1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1.2", "0.1.1"), 1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1.2", "0.1.2"), 0);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("2", "2.3"), -1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("2.0.1", "2"), 1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version(".1", ".2"), -1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("..2", "..1"), 1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("..2.3.4", "..2.3.1"), 1);
	CU_ASSERT_EQUAL(leetcode_165_compare_version("1", "1.1"), -1);
}

static void _168_convert_to_title(void)
{
	CU_ASSERT_PTR_NULL(leetcode_168_convert_to_title(-1));
	CU_ASSERT_PTR_NULL(leetcode_168_convert_to_title(0));
	CU_ASSERT_PTR_NOT_NULL(leetcode_168_convert_to_title(1));
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(1), "A"), 0);
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(2), "B"), 0);
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(3), "C"), 0);
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(26), "Z"), 0);
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(27), "AA"), 0);
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(28), "AB"), 0);
	CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(24568), "AJHX"), 0);
}

static void _169_majority_element(void)
{
	int A[] = {3, 2, 3, 3, 1};
	CU_ASSERT_EQUAL(leetcode_169_majority_element(A, ARRAY_NUM(A)), 3);
}

static void _170_two_sum(void)
{
#if 0
	TwoSum* ts = NULL;

	CU_ASSERT_PTR_NOT_NULL(ts = leetcode_170_two_sum());
	ts->add(ts, 1);
	ts->add(ts, 3);
	ts->add(ts, 5);
	CU_ASSERT_EQUAL(true, ts->find(ts, 4));
	CU_ASSERT_EQUAL(false, ts->find(ts, 7));
	CU_ASSERT_EQUAL(true, ts->find(ts, 6));
	CU_ASSERT_EQUAL(false, ts->find(ts, 10));
	ts->add(ts, 5);
	CU_ASSERT_EQUAL(true, ts->find(ts, 10));
	TwoSumFree(ts);
#endif
}

static void _171_title_to_number(void)
{
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("A"), 1);
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("B"), 2);
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("C"), 3);
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("Z"), 26);
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("AA"), 27);
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("AB"), 28);
	CU_ASSERT_EQUAL(leetcode_171_title_to_number("AAA"), 703);
}

static void _172_trailing_zeroes(void)
{
	CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(1), 0);
	CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(5), 1);
	CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(6), 1);
	CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(20),4);
}

static void _179_largest_number(void)
{
	int a0[] = {1, 2};
	int a1[] = {2, 2};
	int a2[] = {3, 30};
	int a3[] = {3, 34};
	int a4[] = {43, 435};
	int a5[] = {0, 0};
	int a6[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
	int a7[] = {0, 1};
	int a8[] = {1, 0};
	int a9[] = {7543,5328,9834,1940,9387,871,5208,7,543};
	int a10[] = {3, 30, 34, 5, 9};
	int a11[] = {883,8};
	int a12[] = {1440,7548,4240,6616,733,4712,883,8,9576};
	int a13[] = {3, 33, 32};
	int a14[] = {3,43,48,94,85,33,64,32,63,66};
	char* s = NULL;

	s = leetcode_179_largest_number(a0, ARRAY_NUM(a0));
	CU_ASSERT_EQUAL(0, strcmp(s, "21"));

	s = leetcode_179_largest_number(a1, ARRAY_NUM(a1));
	CU_ASSERT_EQUAL(0, strcmp(s, "22"));

	s = leetcode_179_largest_number(a2, ARRAY_NUM(a2));
	CU_ASSERT_EQUAL(0, strcmp(s, "330"));

	s = leetcode_179_largest_number(a3, ARRAY_NUM(a3));
	CU_ASSERT_EQUAL(0, strcmp(s, "343"));

	s = leetcode_179_largest_number(a4, ARRAY_NUM(a4));
	CU_ASSERT_EQUAL(0, strcmp(s, "43543"));

	s = leetcode_179_largest_number(a5, ARRAY_NUM(a5));
	CU_ASSERT_EQUAL(0, strcmp(s, "0"));

	s = leetcode_179_largest_number(a6, ARRAY_NUM(a6));
	CU_ASSERT_EQUAL(0, strcmp(s, "9876543210"));

	s = leetcode_179_largest_number(a7, ARRAY_NUM(a7));
	CU_ASSERT_EQUAL(0, strcmp(s, "10"));

	s = leetcode_179_largest_number(a8, ARRAY_NUM(a8));
	CU_ASSERT_EQUAL(0, strcmp(s, "10"));

	s = leetcode_179_largest_number(a9, ARRAY_NUM(a9));
	CU_ASSERT_EQUAL(0, strcmp(s, "9834938787177543543532852081940"));

	s = leetcode_179_largest_number(a10, ARRAY_NUM(a10));
	CU_ASSERT_EQUAL(0, strcmp(s, "9534330"));

	s = leetcode_179_largest_number(a11, ARRAY_NUM(a11));
	CU_ASSERT_EQUAL(0, strcmp(s, "8883"));

	s = leetcode_179_largest_number(a12, ARRAY_NUM(a12));
	CU_ASSERT_EQUAL(0, strcmp(s, "9576888375487336616471242401440"));

	s = leetcode_179_largest_number(a13, ARRAY_NUM(a13));
	CU_ASSERT_EQUAL(0, strcmp(s, "33332"));
	printf("s = %s\n", s);

	s = leetcode_179_largest_number(a14, ARRAY_NUM(a14));
	CU_ASSERT_EQUAL(0, strcmp(s, "9485666463484333332"));
	printf("s = %s\n", s);
}

unsigned hanming_dist(const unsigned char *vec1, const unsigned char *vec2, unsigned dim)
{
	unsigned i = 0;
	const unsigned char popCountTable[] =
	{
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
	};
	unsigned dist_ = 0;
	for(i = 0; i != dim; ++i)
	{
		dist_ += popCountTable[vec1[i] ^ vec2[i]];
	}
	return dist_;
}

int get_key_line_number(const char* file, const char* key, char* out)
{
	FILE * pf = NULL;
	char string[256] = {0};
	size_t result = 0;
	size_t index = 0;
	size_t row = 0;
	size_t col = 0;
	size_t offset = 0;
	char* pos = NULL;
	char* p = NULL;

	if((file == NULL) || (key == NULL))
	{
		return -1;
	}

	if((*file == '\0') || (*key == '\0'))
	{
		return -2;
	}

	pf = fopen(file , "r");
	if(pf == NULL)
	{
		perror("Error opening file");
		return -3;
	}

	do
	{
		memset(string, 0, sizeof(string));
		result = fread(string, 1, sizeof(string) - 1, pf);
		pos = strstr(string, key);
		p = string;
		offset = (size_t)(pos - string);
		for(index = 0; (index < sizeof(string) - 1) && (*p != '\0'); index++)
		{
			if((pos != NULL) && (offset == index))
			{
				out += sprintf(out, "row:%d+col:%d ", row, col);
				pos = strstr(string + offset + strlen(key), key);
				offset = (size_t)(pos - string);
			}

			if(string[index] == (char)'\n')
			{
				row++;
				col = 0;
			}
			else
			{
				col++;
			}
			p++;
		}
	}while(!feof(pf));


	fclose (pf);
	return 0;
}

static void puts_string_to_file(const char* string, const char* file)
{
	FILE* fp = NULL;
	if((string == NULL) || (file == NULL)) return;
	if(*string == '\0' || (*file == '\0')) return;

	fp = fopen(file, "w");
	fwrite(string, 1, strlen(string), fp);
	fclose(fp);
}

static void _998_get_string_line_number(void)
{
	char out[1024] = {0};
	const char* str1 = "456123\n123\n123123\n23\n13";
	const char* key1 = "123";
	const char* str2 = "456123\n123\n123123\n23\n13";
	const char* key2 = "23";

	memset(out, 0, sizeof(out));
	puts_string_to_file(str1, "abc.txt");
	CU_ASSERT_EQUAL(get_key_line_number("abc.txt", key1, out), 0);
	CU_ASSERT_EQUAL(strcmp(out, "row:0+col:3 row:1+col:0 row:2+col:0 row:2+col:3 "), 0);
	CU_ASSERT_EQUAL(remove("abc.txt"), 0);

	memset(out, 0, sizeof(out));
	puts_string_to_file(str2, "abc.txt");
	CU_ASSERT_EQUAL(get_key_line_number("abc.txt", key2, out), 0);
}

static void _999_oj_binary_tree_serialization(void)
{
	TreeNode* t1 = NULL;
	TreeNode* t2 = NULL;

	t1 = TreeNewByStringOJ("{1,2,3,#,#,4,#,#,5}");
	t2 = TreeNewByString("1,2,#,#,3,4,#,5,#,#,");
	CU_ASSERT_EQUAL(isSameTree(t1, t2), true);
	t1 = TreeDestroy(t1);
	t2 = TreeDestroy(t2);
}

/*****************************************************************************
 * 注册测试用例.
 ****************************************************************************/
static CU_TestInfo g_leetcode_test_case[] =
{
	{"  2:Add Two Numbers",                       _002_add_two_numbers},
	{"  6:ZigZag Conversion",                     _006_convert},
	{"  7:Reverse Intege",                        _007_reverse},
	{"  8:String to Integer (atoi)",              _008_atoi},
	{"  9:Palindrome Number",                     _009_is_palindrome},
	{" 13:Roman to Integer",                      _013_roman_to_int},
	{" 14:Longest Common Prefix",                 _014_longest_common_prefix},
	{" 19:Remove Nth Node From End of List",      _019_remove_nth_node_from_end},
	{" 20:Valid Parentheses",                     _020_is_valid},
	{" 21:Merge Two Sorted Lists",                _021_merge_two_sorted_lists},
	{" 24:Swap Nodes in Pairs",                   _024_swap_pairs},
	{" 26:Remove Duplicates from Sorted Array",   _026_remove_duplicates},
	{" 27:Remove Element",                        _027_remove_element},
	{" 28:Implement strstr",                      _028_implement_strstr},
	{" 36:Valid Sudoku",                          _036_is_valid_sudoku},
	{" 38:Count and Say",                         _038_count_and_say},
	{" 58:Length of Last Word",                   _058_length_of_last_word},
	{" 61:Rotate List",                           _061_rotate_right},
	{" 66:Plus One",                              _066_plus_one},
	{" 67:Add Binary",                            _067_add_binary},
	{" 70:Climbing Stairs",                       _070_climb_stairs},
	{" 78:Subsets",                               _078_subsets},
	{" 82:Remove Duplicates from Sorted List II", _082_delete_duplicates_ii},
	{" 83:Remove Duplicates from Sorted List",    _083_delete_duplicates},
	{" 86:Partition List",                        _086_partition_list},
	{" 88:Merge Sorted Array",                    _088_merge_sorted_array},
	{" 92:Reverse Linked List II",                _092_reverse_between},
	{" 94:Binary Tree Inorder Traversal",         _094_inorder_traversal},
	{" 98:Validate Binary Search Tree",           _098_is_valid_bst},
	{"100:Same Tree",                             _100_same_tree},
	{"101:Symmetric Tree ",                       _101_is_symmetric},
	{"102:Binary Tree Level Order Traversal",     _102_level_order},
	{"104:Maximum Depth of Binary Tree",          _104_max_depth},
	{"107:Binary Tree Level Order Traversal II",  _107_level_order_bottom},
	{"110:Balanced Binary Tree ",                 _110_lbe_is_balanced},
	{"111:Minimum Depth of Binary Tree",          _111_min_depth},
	{"112:Path Sum",                              _112_path_sum},
	{"114:Flatten Binary Tree to Linked List",    _114_flatten},
	{"116:Populating Next Right Pointers in Each Node", _116_connect},
	{"118:Pascal's Triangle",                     _118_generate},
	{"119:Pascal's Triangle II",                  _119_get_row},
	{"125:Valid Palindrome",                      _125_is_palindrome},
	{"136:Single Number",                         _136_single_number},
	{"137:Single Number II",                      _137_single_number_ii},
	{"141:Linked List Cycle",                     _141_has_cycle},
	{"142:Linked List Cycle II",                  _142_detect_cycle},
	{"143:Reorder List",                          _143_reorder_list},
	{"144:Binary Tree Preorder Traversal ",       _144_preorder_traversal},
	{"147:Insertion Sort List",                   _147_insertion_sort_list},
	{"155:Min Stack",                             _155_min_stack},
	{"160:Intersection of Two Linked Lists ",     _160_intersection_linked_list},
	{"165:Compare Version Numbers",               _165_compare_version},
	{"168:Excel Sheet Column Title",              _168_convert_to_title},
	{"169:Majority Element",                      _169_majority_element},
	{"170:Two Sum III - Data structure design",   _170_two_sum},
	{"171:Excel Sheet Column Number",             _171_title_to_number},
	{"172:Factorial Trailing Zeroes",             _172_trailing_zeroes},
	{"179:Largest Number",                        _179_largest_number},
	{"998:Get String Line Number",                _998_get_string_line_number},
	{"999:OJ's Binary Tree Serialization",        _999_oj_binary_tree_serialization},
	CU_TEST_INFO_NULL,
};

static CU_SuiteInfo suites[] =
{
    {"leetcode",  NULL, NULL, NULL, NULL, g_leetcode_test_case},
	CU_SUITE_INFO_NULL,
};

int main(int argc, char* argv[]) 
{
	if(CUE_SUCCESS != CU_initialize_registry())
	{
		return CU_get_error();
	}

	if(CU_register_suites(suites) != CUE_SUCCESS)
	{
		printf("suite registration failed - %s\n", CU_get_error_msg());
		return CU_get_error();
	}

	CU_basic_set_mode(CU_BRM_VERBOSE);
	CU_basic_run_tests();
	CU_cleanup_registry();

	return CU_get_error();
}

